Alexander Afanasyev | 78057c3 | 2012-07-06 15:18:46 -0700 | [diff] [blame] | 1 | /* -*- 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 Afanasyev | 4aac557 | 2012-08-09 10:49:55 -0700 | [diff] [blame] | 21 | #include "ndn-fib-impl.h" |
Alexander Afanasyev | 78057c3 | 2012-07-06 15:18:46 -0700 | [diff] [blame] | 22 | |
Alexander Afanasyev | 4aac557 | 2012-08-09 10:49:55 -0700 | [diff] [blame] | 23 | #include "ns3/ndn.h" |
| 24 | #include "ns3/ndn-face.h" |
| 25 | #include "ns3/ndn-interest-header.h" |
Alexander Afanasyev | 78057c3 | 2012-07-06 15:18:46 -0700 | [diff] [blame] | 26 | |
| 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> |
| 35 | namespace ll = boost::lambda; |
| 36 | |
Alexander Afanasyev | 2b4c947 | 2012-08-09 15:00:38 -0700 | [diff] [blame^] | 37 | NS_LOG_COMPONENT_DEFINE ("ndn.fib.FibImpl"); |
Alexander Afanasyev | 78057c3 | 2012-07-06 15:18:46 -0700 | [diff] [blame] | 38 | |
| 39 | namespace ns3 { |
Alexander Afanasyev | 2b4c947 | 2012-08-09 15:00:38 -0700 | [diff] [blame^] | 40 | namespace ndn { |
| 41 | namespace fib { |
Alexander Afanasyev | 78057c3 | 2012-07-06 15:18:46 -0700 | [diff] [blame] | 42 | |
Alexander Afanasyev | 2b4c947 | 2012-08-09 15:00:38 -0700 | [diff] [blame^] | 43 | NS_OBJECT_ENSURE_REGISTERED (FibImpl); |
Alexander Afanasyev | 78057c3 | 2012-07-06 15:18:46 -0700 | [diff] [blame] | 44 | |
| 45 | TypeId |
Alexander Afanasyev | 2b4c947 | 2012-08-09 15:00:38 -0700 | [diff] [blame^] | 46 | FibImpl::GetTypeId (void) |
Alexander Afanasyev | 78057c3 | 2012-07-06 15:18:46 -0700 | [diff] [blame] | 47 | { |
Alexander Afanasyev | 2b4c947 | 2012-08-09 15:00:38 -0700 | [diff] [blame^] | 48 | static TypeId tid = TypeId ("ns3::ndn::fib::Default") // cheating ns3 object system |
| 49 | .SetParent<Fib> () |
Alexander Afanasyev | 4aac557 | 2012-08-09 10:49:55 -0700 | [diff] [blame] | 50 | .SetGroupName ("Ndn") |
Alexander Afanasyev | 2b4c947 | 2012-08-09 15:00:38 -0700 | [diff] [blame^] | 51 | .AddConstructor<FibImpl> () |
Alexander Afanasyev | 78057c3 | 2012-07-06 15:18:46 -0700 | [diff] [blame] | 52 | ; |
| 53 | return tid; |
| 54 | } |
| 55 | |
Alexander Afanasyev | 2b4c947 | 2012-08-09 15:00:38 -0700 | [diff] [blame^] | 56 | FibImpl::FibImpl () |
Alexander Afanasyev | 78057c3 | 2012-07-06 15:18:46 -0700 | [diff] [blame] | 57 | { |
| 58 | } |
| 59 | |
| 60 | void |
Alexander Afanasyev | 2b4c947 | 2012-08-09 15:00:38 -0700 | [diff] [blame^] | 61 | FibImpl::NotifyNewAggregate () |
Alexander Afanasyev | 78057c3 | 2012-07-06 15:18:46 -0700 | [diff] [blame] | 62 | { |
| 63 | Object::NotifyNewAggregate (); |
| 64 | } |
| 65 | |
| 66 | void |
Alexander Afanasyev | 2b4c947 | 2012-08-09 15:00:38 -0700 | [diff] [blame^] | 67 | FibImpl::DoDispose (void) |
Alexander Afanasyev | 78057c3 | 2012-07-06 15:18:46 -0700 | [diff] [blame] | 68 | { |
| 69 | clear (); |
| 70 | Object::DoDispose (); |
| 71 | } |
| 72 | |
| 73 | |
Alexander Afanasyev | 2b4c947 | 2012-08-09 15:00:38 -0700 | [diff] [blame^] | 74 | Ptr<Entry> |
| 75 | FibImpl::LongestPrefixMatch (const InterestHeader &interest) |
Alexander Afanasyev | 78057c3 | 2012-07-06 15:18:46 -0700 | [diff] [blame] | 76 | { |
Alexander Afanasyev | 30f60e3 | 2012-07-10 14:21:16 -0700 | [diff] [blame] | 77 | super::iterator item = super::longest_prefix_match (interest.GetName ()); |
Alexander Afanasyev | 78057c3 | 2012-07-06 15:18:46 -0700 | [diff] [blame] | 78 | // @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 | |
| 86 | |
Alexander Afanasyev | 2b4c947 | 2012-08-09 15:00:38 -0700 | [diff] [blame^] | 87 | Ptr<Entry> |
| 88 | FibImpl::Add (const NameComponents &prefix, Ptr<Face> face, int32_t metric) |
Alexander Afanasyev | 78057c3 | 2012-07-06 15:18:46 -0700 | [diff] [blame] | 89 | { |
Alexander Afanasyev | 2b4c947 | 2012-08-09 15:00:38 -0700 | [diff] [blame^] | 90 | return Add (Create<NameComponents> (prefix), face, metric); |
Alexander Afanasyev | 78057c3 | 2012-07-06 15:18:46 -0700 | [diff] [blame] | 91 | } |
| 92 | |
Alexander Afanasyev | 2b4c947 | 2012-08-09 15:00:38 -0700 | [diff] [blame^] | 93 | Ptr<Entry> |
| 94 | FibImpl::Add (const Ptr<const NameComponents> &prefix, Ptr<Face> face, int32_t metric) |
Alexander Afanasyev | 78057c3 | 2012-07-06 15:18:46 -0700 | [diff] [blame] | 95 | { |
Alexander Afanasyev | 1ba09b8 | 2012-07-09 09:16:14 -0700 | [diff] [blame] | 96 | NS_LOG_FUNCTION (this->GetObject<Node> ()->GetId () << boost::cref(*prefix) << boost::cref(*face) << metric); |
Alexander Afanasyev | 78057c3 | 2012-07-06 15:18:46 -0700 | [diff] [blame] | 97 | |
| 98 | // will add entry if doesn't exists, or just return an iterator to the existing entry |
Alexander Afanasyev | 30f60e3 | 2012-07-10 14:21:16 -0700 | [diff] [blame] | 99 | std::pair< super::iterator, bool > result = super::insert (*prefix, 0); |
| 100 | if (result.first != super::end ()) |
| 101 | { |
| 102 | if (result.second) |
| 103 | { |
Alexander Afanasyev | 2b4c947 | 2012-08-09 15:00:38 -0700 | [diff] [blame^] | 104 | Ptr<EntryImpl> newEntry = Create<EntryImpl> (prefix); |
Alexander Afanasyev | 30f60e3 | 2012-07-10 14:21:16 -0700 | [diff] [blame] | 105 | newEntry->SetTrie (result.first); |
| 106 | result.first->set_payload (newEntry); |
| 107 | } |
Alexander Afanasyev | 78057c3 | 2012-07-06 15:18:46 -0700 | [diff] [blame] | 108 | |
Alexander Afanasyev | 30f60e3 | 2012-07-10 14:21:16 -0700 | [diff] [blame] | 109 | super::modify (result.first, |
Alexander Afanasyev | 2b4c947 | 2012-08-09 15:00:38 -0700 | [diff] [blame^] | 110 | ll::bind (&Entry::AddOrUpdateRoutingMetric, ll::_1, face, metric)); |
Alexander Afanasyev | 78057c3 | 2012-07-06 15:18:46 -0700 | [diff] [blame] | 111 | |
Alexander Afanasyev | 30f60e3 | 2012-07-10 14:21:16 -0700 | [diff] [blame] | 112 | return result.first->payload (); |
| 113 | } |
| 114 | else |
| 115 | return 0; |
Alexander Afanasyev | 78057c3 | 2012-07-06 15:18:46 -0700 | [diff] [blame] | 116 | } |
| 117 | |
| 118 | void |
Alexander Afanasyev | 2b4c947 | 2012-08-09 15:00:38 -0700 | [diff] [blame^] | 119 | FibImpl::Remove (const Ptr<const NameComponents> &prefix) |
Alexander Afanasyev | 78057c3 | 2012-07-06 15:18:46 -0700 | [diff] [blame] | 120 | { |
| 121 | NS_LOG_FUNCTION (this->GetObject<Node> ()->GetId () << boost::cref(*prefix)); |
| 122 | |
| 123 | super::erase (*prefix); |
| 124 | } |
| 125 | |
Alexander Afanasyev | 44bb6ea | 2012-07-09 08:44:41 -0700 | [diff] [blame] | 126 | // void |
Alexander Afanasyev | 2b4c947 | 2012-08-09 15:00:38 -0700 | [diff] [blame^] | 127 | // FibImpl::Invalidate (const Ptr<const NameComponents> &prefix) |
Alexander Afanasyev | 44bb6ea | 2012-07-09 08:44:41 -0700 | [diff] [blame] | 128 | // { |
| 129 | // NS_LOG_FUNCTION (this->GetObject<Node> ()->GetId () << boost::cref(*prefix)); |
Alexander Afanasyev | 78057c3 | 2012-07-06 15:18:46 -0700 | [diff] [blame] | 130 | |
Alexander Afanasyev | 44bb6ea | 2012-07-09 08:44:41 -0700 | [diff] [blame] | 131 | // super::iterator foundItem, lastItem; |
| 132 | // bool reachLast; |
| 133 | // boost::tie (foundItem, reachLast, lastItem) = super::getTrie ().find (*prefix); |
Alexander Afanasyev | 78057c3 | 2012-07-06 15:18:46 -0700 | [diff] [blame] | 134 | |
Alexander Afanasyev | 44bb6ea | 2012-07-09 08:44:41 -0700 | [diff] [blame] | 135 | // if (!reachLast || lastItem->payload () == 0) |
| 136 | // return; // nothing to invalidate |
Alexander Afanasyev | 78057c3 | 2012-07-06 15:18:46 -0700 | [diff] [blame] | 137 | |
Alexander Afanasyev | 44bb6ea | 2012-07-09 08:44:41 -0700 | [diff] [blame] | 138 | // super::modify (lastItem, |
Alexander Afanasyev | 2b4c947 | 2012-08-09 15:00:38 -0700 | [diff] [blame^] | 139 | // ll::bind (&Entry::Invalidate, ll::_1)); |
Alexander Afanasyev | 44bb6ea | 2012-07-09 08:44:41 -0700 | [diff] [blame] | 140 | // } |
Alexander Afanasyev | 78057c3 | 2012-07-06 15:18:46 -0700 | [diff] [blame] | 141 | |
| 142 | void |
Alexander Afanasyev | 2b4c947 | 2012-08-09 15:00:38 -0700 | [diff] [blame^] | 143 | FibImpl::InvalidateAll () |
Alexander Afanasyev | 78057c3 | 2012-07-06 15:18:46 -0700 | [diff] [blame] | 144 | { |
Alexander Afanasyev | 44bb6ea | 2012-07-09 08:44:41 -0700 | [diff] [blame] | 145 | NS_LOG_FUNCTION (this->GetObject<Node> ()->GetId ()); |
Alexander Afanasyev | 78057c3 | 2012-07-06 15:18:46 -0700 | [diff] [blame] | 146 | |
Alexander Afanasyev | 44bb6ea | 2012-07-09 08:44:41 -0700 | [diff] [blame] | 147 | super::parent_trie::recursive_iterator item (super::getTrie ()); |
| 148 | super::parent_trie::recursive_iterator end (0); |
| 149 | for (; item != end; item++) |
| 150 | { |
| 151 | if (item->payload () == 0) continue; |
| 152 | |
| 153 | super::modify (&(*item), |
Alexander Afanasyev | 2b4c947 | 2012-08-09 15:00:38 -0700 | [diff] [blame^] | 154 | ll::bind (&Entry::Invalidate, ll::_1)); |
Alexander Afanasyev | 44bb6ea | 2012-07-09 08:44:41 -0700 | [diff] [blame] | 155 | } |
Alexander Afanasyev | 78057c3 | 2012-07-06 15:18:46 -0700 | [diff] [blame] | 156 | } |
| 157 | |
| 158 | void |
Alexander Afanasyev | 2b4c947 | 2012-08-09 15:00:38 -0700 | [diff] [blame^] | 159 | FibImpl::RemoveFace (super::parent_trie &item, Ptr<Face> face) |
Alexander Afanasyev | 78057c3 | 2012-07-06 15:18:46 -0700 | [diff] [blame] | 160 | { |
Alexander Afanasyev | 44bb6ea | 2012-07-09 08:44:41 -0700 | [diff] [blame] | 161 | if (item.payload () == 0) return; |
| 162 | NS_LOG_FUNCTION (this); |
Alexander Afanasyev | 78057c3 | 2012-07-06 15:18:46 -0700 | [diff] [blame] | 163 | |
Alexander Afanasyev | 44bb6ea | 2012-07-09 08:44:41 -0700 | [diff] [blame] | 164 | super::modify (&item, |
Alexander Afanasyev | 2b4c947 | 2012-08-09 15:00:38 -0700 | [diff] [blame^] | 165 | ll::bind (&Entry::RemoveFace, ll::_1, face)); |
Alexander Afanasyev | 78057c3 | 2012-07-06 15:18:46 -0700 | [diff] [blame] | 166 | } |
| 167 | |
| 168 | void |
Alexander Afanasyev | 2b4c947 | 2012-08-09 15:00:38 -0700 | [diff] [blame^] | 169 | FibImpl::RemoveFromAll (Ptr<Face> face) |
Alexander Afanasyev | 78057c3 | 2012-07-06 15:18:46 -0700 | [diff] [blame] | 170 | { |
Alexander Afanasyev | 44bb6ea | 2012-07-09 08:44:41 -0700 | [diff] [blame] | 171 | NS_LOG_FUNCTION (this); |
Alexander Afanasyev | 78057c3 | 2012-07-06 15:18:46 -0700 | [diff] [blame] | 172 | |
Alexander Afanasyev | 44bb6ea | 2012-07-09 08:44:41 -0700 | [diff] [blame] | 173 | std::for_each (super::parent_trie::recursive_iterator (super::getTrie ()), |
| 174 | super::parent_trie::recursive_iterator (0), |
Alexander Afanasyev | 2b4c947 | 2012-08-09 15:00:38 -0700 | [diff] [blame^] | 175 | ll::bind (&FibImpl::RemoveFace, |
Alexander Afanasyev | 44bb6ea | 2012-07-09 08:44:41 -0700 | [diff] [blame] | 176 | this, ll::_1, face)); |
| 177 | |
| 178 | super::parent_trie::recursive_iterator trieNode (super::getTrie ()); |
| 179 | super::parent_trie::recursive_iterator end (0); |
| 180 | for (; trieNode != end; trieNode++) |
| 181 | { |
| 182 | if (trieNode->payload () == 0) continue; |
| 183 | |
| 184 | if (trieNode->payload ()->m_faces.size () == 0) |
| 185 | { |
| 186 | trieNode = super::parent_trie::recursive_iterator (trieNode->erase ()); |
| 187 | } |
| 188 | } |
Alexander Afanasyev | 78057c3 | 2012-07-06 15:18:46 -0700 | [diff] [blame] | 189 | } |
| 190 | |
| 191 | void |
Alexander Afanasyev | 2b4c947 | 2012-08-09 15:00:38 -0700 | [diff] [blame^] | 192 | FibImpl::Print (std::ostream &os) const |
Alexander Afanasyev | 78057c3 | 2012-07-06 15:18:46 -0700 | [diff] [blame] | 193 | { |
Alexander Afanasyev | 44bb6ea | 2012-07-09 08:44:41 -0700 | [diff] [blame] | 194 | // !!! unordered_set imposes "random" order of item in the same level !!! |
| 195 | super::parent_trie::const_recursive_iterator item (super::getTrie ()); |
| 196 | super::parent_trie::const_recursive_iterator end (0); |
| 197 | for (; item != end; item++) |
| 198 | { |
| 199 | if (item->payload () == 0) continue; |
| 200 | |
| 201 | os << item->payload ()->GetPrefix () << "\t" << *item->payload () << "\n"; |
| 202 | } |
Alexander Afanasyev | 78057c3 | 2012-07-06 15:18:46 -0700 | [diff] [blame] | 203 | } |
| 204 | |
Alexander Afanasyev | f1e013f | 2012-07-11 17:59:40 -0700 | [diff] [blame] | 205 | uint32_t |
Alexander Afanasyev | 2b4c947 | 2012-08-09 15:00:38 -0700 | [diff] [blame^] | 206 | FibImpl::GetSize () const |
Alexander Afanasyev | f1e013f | 2012-07-11 17:59:40 -0700 | [diff] [blame] | 207 | { |
| 208 | return super::getPolicy ().size (); |
| 209 | } |
| 210 | |
Alexander Afanasyev | 2b4c947 | 2012-08-09 15:00:38 -0700 | [diff] [blame^] | 211 | Ptr<const Entry> |
| 212 | FibImpl::Begin () |
Alexander Afanasyev | 95a4fa3 | 2012-07-09 15:23:59 -0700 | [diff] [blame] | 213 | { |
| 214 | super::parent_trie::const_recursive_iterator item (super::getTrie ()); |
| 215 | super::parent_trie::const_recursive_iterator end (0); |
| 216 | for (; item != end; item++) |
| 217 | { |
| 218 | if (item->payload () == 0) continue; |
| 219 | break; |
| 220 | } |
| 221 | |
| 222 | if (item == end) |
| 223 | return End (); |
| 224 | else |
| 225 | return item->payload (); |
| 226 | } |
| 227 | |
Alexander Afanasyev | 2b4c947 | 2012-08-09 15:00:38 -0700 | [diff] [blame^] | 228 | Ptr<const Entry> |
| 229 | FibImpl::End () |
Alexander Afanasyev | 95a4fa3 | 2012-07-09 15:23:59 -0700 | [diff] [blame] | 230 | { |
| 231 | return 0; |
| 232 | } |
| 233 | |
Alexander Afanasyev | 2b4c947 | 2012-08-09 15:00:38 -0700 | [diff] [blame^] | 234 | Ptr<const Entry> |
| 235 | FibImpl::Next (Ptr<const Entry> from) |
Alexander Afanasyev | 95a4fa3 | 2012-07-09 15:23:59 -0700 | [diff] [blame] | 236 | { |
| 237 | if (from == 0) return 0; |
| 238 | |
Alexander Afanasyev | 2b4c947 | 2012-08-09 15:00:38 -0700 | [diff] [blame^] | 239 | super::parent_trie::const_recursive_iterator item (*StaticCast<const EntryImpl> (from)->to_iterator ()); |
Alexander Afanasyev | 95a4fa3 | 2012-07-09 15:23:59 -0700 | [diff] [blame] | 240 | super::parent_trie::const_recursive_iterator end (0); |
| 241 | for (item++; item != end; item++) |
| 242 | { |
| 243 | if (item->payload () == 0) continue; |
| 244 | break; |
| 245 | } |
| 246 | |
| 247 | if (item == end) |
| 248 | return End (); |
| 249 | else |
| 250 | return item->payload (); |
| 251 | } |
| 252 | |
Alexander Afanasyev | 2b4c947 | 2012-08-09 15:00:38 -0700 | [diff] [blame^] | 253 | } // namespace fib |
| 254 | } // namespace ndn |
Alexander Afanasyev | 78057c3 | 2012-07-06 15:18:46 -0700 | [diff] [blame] | 255 | } // namespace ns3 |