NS-3 based Named Data Networking (NDN) simulator
ndnSIM: NDN, CCN, CCNx, content centric networks
API Documentation
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
trie-with-policy.h
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 
21 #ifndef TRIE_WITH_POLICY_H_
22 #define TRIE_WITH_POLICY_H_
23 
24 #include "trie.h"
25 
26 namespace ns3 {
27 namespace ndn {
28 namespace ndnSIM {
29 
30 template<typename FullKey,
31  typename PayloadTraits,
32  typename PolicyTraits
33  >
35 {
36 public:
37  typedef trie< FullKey,
38  PayloadTraits,
39  typename PolicyTraits::policy_hook_type > parent_trie;
40 
41  typedef typename parent_trie::iterator iterator;
43 
44  typedef typename PolicyTraits::template policy<
47  typename PolicyTraits::template container_hook<parent_trie>::type >::type policy_container;
48 
49  inline
50  trie_with_policy (size_t bucketSize = 1, size_t bucketIncrement = 1)
51  : trie_ (name::Component (), bucketSize, bucketIncrement)
52  , policy_ (*this)
53  {
54  }
55 
56  inline std::pair< iterator, bool >
57  insert (const FullKey &key, typename PayloadTraits::insert_type payload)
58  {
59  std::pair<iterator, bool> item =
60  trie_.insert (key, payload);
61 
62  if (item.second) // real insert
63  {
64  bool ok = policy_.insert (s_iterator_to (item.first));
65  if (!ok)
66  {
67  item.first->erase (); // cannot insert
68  return std::make_pair (end (), false);
69  }
70  }
71  else
72  {
73  return std::make_pair (s_iterator_to (item.first), false);
74  }
75 
76  return item;
77  }
78 
79  inline void
80  erase (const FullKey &key)
81  {
82  iterator foundItem, lastItem;
83  bool reachLast;
84  boost::tie (foundItem, reachLast, lastItem) = trie_.find (key);
85 
86  if (!reachLast || lastItem->payload () == PayloadTraits::empty_payload)
87  return; // nothing to invalidate
88 
89  erase (lastItem);
90  }
91 
92  inline void
93  erase (iterator node)
94  {
95  if (node == end ()) return;
96 
97  policy_.erase (s_iterator_to (node));
98  node->erase (); // will do cleanup here
99  }
100 
101  inline void
102  clear ()
103  {
104  policy_.clear ();
105  trie_.clear ();
106  }
107 
108  template<typename Modifier>
109  bool
110  modify (iterator position, Modifier mod)
111  {
112  if (position == end ()) return false;
113  if (position->payload () == PayloadTraits::empty_payload) return false;
114 
115  mod (*position->payload ());
116  policy_.update (position);
117  return true;
118  }
119 
123  inline iterator
124  find_exact (const FullKey &key)
125  {
126  iterator foundItem, lastItem;
127  bool reachLast;
128  boost::tie (foundItem, reachLast, lastItem) = trie_.find (key);
129 
130  if (!reachLast || lastItem->payload () == PayloadTraits::empty_payload)
131  return end ();
132 
133  return lastItem;
134  }
135 
139  inline iterator
140  longest_prefix_match (const FullKey &key)
141  {
142  iterator foundItem, lastItem;
143  bool reachLast;
144  boost::tie (foundItem, reachLast, lastItem) = trie_.find (key);
145  if (foundItem != trie_.end ())
146  {
147  policy_.lookup (s_iterator_to (foundItem));
148  }
149  return foundItem;
150  }
151 
155  template<class Predicate>
156  inline iterator
157  longest_prefix_match_if (const FullKey &key, Predicate pred)
158  {
159  iterator foundItem, lastItem;
160  bool reachLast;
161  boost::tie (foundItem, reachLast, lastItem) = trie_.find_if (key, pred);
162  if (foundItem != trie_.end ())
163  {
164  policy_.lookup (s_iterator_to (foundItem));
165  }
166  return foundItem;
167  }
168 
169  // /**
170  // * @brief Const version of the longest common prefix match
171  // * (semi-const, because there could be update of the policy anyways)
172  // */
173  // inline const_iterator
174  // longest_prefix_match (const FullKey &key) const
175  // {
176  // return static_cast<trie_with_policy*> (this)->longest_prefix_match (key);
177  // }
178 
182  inline iterator
183  deepest_prefix_match (const FullKey &key)
184  {
185  iterator foundItem, lastItem;
186  bool reachLast;
187  boost::tie (foundItem, reachLast, lastItem) = trie_.find (key);
188 
189  // guard in case we don't have anything in the trie
190  if (lastItem == trie_.end ())
191  return trie_.end ();
192 
193  if (reachLast)
194  {
195  if (foundItem == trie_.end ())
196  {
197  foundItem = lastItem->find (); // should be something
198  }
199  policy_.lookup (s_iterator_to (foundItem));
200  return foundItem;
201  }
202  else
203  { // couldn't find a node that has prefix at least as key
204  return trie_.end ();
205  }
206  }
207 
211  template<class Predicate>
212  inline iterator
213  deepest_prefix_match_if (const FullKey &key, Predicate pred)
214  {
215  iterator foundItem, lastItem;
216  bool reachLast;
217  boost::tie (foundItem, reachLast, lastItem) = trie_.find (key);
218 
219  // guard in case we don't have anything in the trie
220  if (lastItem == trie_.end ())
221  return trie_.end ();
222 
223  if (reachLast)
224  {
225  foundItem = lastItem->find_if (pred); // may or may not find something
226  if (foundItem == trie_.end ())
227  {
228  return trie_.end ();
229  }
230  policy_.lookup (s_iterator_to (foundItem));
231  return foundItem;
232  }
233  else
234  { // couldn't find a node that has prefix at least as key
235  return trie_.end ();
236  }
237  }
238 
245  template<class Predicate>
246  inline iterator
247  deepest_prefix_match_if_next_level (const FullKey &key, Predicate pred)
248  {
249  iterator foundItem, lastItem;
250  bool reachLast;
251  boost::tie (foundItem, reachLast, lastItem) = trie_.find (key);
252 
253  // guard in case we don't have anything in the trie
254  if (lastItem == trie_.end ())
255  return trie_.end ();
256 
257  if (reachLast)
258  {
259  foundItem = lastItem->find_if_next_level (pred); // may or may not find something
260  if (foundItem == trie_.end ())
261  {
262  return trie_.end ();
263  }
264  policy_.lookup (s_iterator_to (foundItem));
265  return foundItem;
266  }
267  else
268  { // couldn't find a node that has prefix at least as key
269  return trie_.end ();
270  }
271  }
272 
273  iterator end () const
274  {
275  return 0;
276  }
277 
278  const parent_trie &
279  getTrie () const { return trie_; }
280 
281  parent_trie &
282  getTrie () { return trie_; }
283 
284  const policy_container &
285  getPolicy () const { return policy_; }
286 
287  policy_container &
288  getPolicy () { return policy_; }
289 
290  static inline iterator
291  s_iterator_to (typename parent_trie::iterator item)
292  {
293  if (item == 0)
294  return 0;
295  else
296  return &(*item);
297  }
298 
299 private:
300  parent_trie trie_;
301  mutable policy_container policy_;
302 };
303 
304 } // ndnSIM
305 } // ndn
306 } // ns3
307 
308 #endif // TRIE_WITH_POLICY_H_
boost::tuple< iterator, bool, iterator > find(const FullKey &key)
Perform the longest prefix match.
Definition: trie.h:305
iterator longest_prefix_match_if(const FullKey &key, Predicate pred)
Find a node that has the longest common prefix with key (FIB/PIT lookup)
const iterator find_if_next_level(Predicate pred)
Find next payload of the sub-trie satisfying the predicate.
Definition: trie.h:428
iterator deepest_prefix_match_if(const FullKey &key, Predicate pred)
Find a node that has prefix at least as the key.
iterator longest_prefix_match(const FullKey &key)
Find a node that has the longest common prefix with key (FIB/PIT lookup)
boost::tuple< iterator, bool, iterator > find_if(const FullKey &key, Predicate pred)
Perform the longest prefix match satisfying preficate.
Definition: trie.h:339
iterator deepest_prefix_match_if_next_level(const FullKey &key, Predicate pred)
Find a node that has prefix at least as the key.
Class to representing binary blob of NDN name component.
iterator deepest_prefix_match(const FullKey &key)
Const version of the longest common prefix match (semi-const, because there could be update of the po...
iterator erase()
Removes payload (if it exists) and if there are no children, prunes parents trie. ...
Definition: trie.h:251
iterator find_exact(const FullKey &key)
Find a node that has the exact match with the key.