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