blob: f09f13b91335264b7df79f623f91efcc43eecdf8 [file] [log] [blame]
Alexander Afanasyev9a989702012-06-29 17:44:00 -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
21#ifndef TRIE_WITH_POLICY_H_
22#define TRIE_WITH_POLICY_H_
23
Alexander Afanasyev0c395372014-12-20 15:54:02 -080024#include "trie.hpp"
Alexander Afanasyev9a989702012-06-29 17:44:00 -070025
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070026namespace ns3 {
27namespace ndn {
28namespace ndnSIM {
Alexander Afanasyev30cb1172012-07-06 10:47:39 -070029
Alexander Afanasyev9a989702012-06-29 17:44:00 -070030template<typename FullKey,
Alexander Afanasyev9a989702012-06-29 17:44:00 -070031 typename PayloadTraits,
32 typename PolicyTraits
33 >
34class trie_with_policy
35{
36public:
Alexander Afanasyev9e96e362012-07-02 23:04:39 -070037 typedef trie< FullKey,
Alexander Afanasyev9e96e362012-07-02 23:04:39 -070038 PayloadTraits,
39 typename PolicyTraits::policy_hook_type > parent_trie;
40
41 typedef typename parent_trie::iterator iterator;
Alexander Afanasyev1ba09b82012-07-09 09:16:14 -070042 typedef typename parent_trie::const_iterator const_iterator;
Alexander Afanasyev9e96e362012-07-02 23:04:39 -070043
44 typedef typename PolicyTraits::template policy<
45 trie_with_policy<FullKey, PayloadTraits, PolicyTraits>,
46 parent_trie,
47 typename PolicyTraits::template container_hook<parent_trie>::type >::type policy_container;
Alexander Afanasyev9a989702012-06-29 17:44:00 -070048
49 inline
Alexander Afanasyevac49cad2013-07-26 11:31:47 -070050 trie_with_policy (size_t bucketSize = 1, size_t bucketIncrement = 1)
Alexander Afanasyev92136012013-07-16 20:36:30 -070051 : trie_ (name::Component (), bucketSize, bucketIncrement)
Alexander Afanasyev9e96e362012-07-02 23:04:39 -070052 , policy_ (*this)
Alexander Afanasyev9a989702012-06-29 17:44:00 -070053 {
54 }
55
56 inline std::pair< iterator, bool >
Alexander Afanasyev0845c092012-07-13 17:45:33 -070057 insert (const FullKey &key, typename PayloadTraits::insert_type payload)
Alexander Afanasyev9a989702012-06-29 17:44:00 -070058 {
59 std::pair<iterator, bool> item =
60 trie_.insert (key, payload);
61
62 if (item.second) // real insert
63 {
Alexander Afanasyev9e96e362012-07-02 23:04:39 -070064 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 }
Alexander Afanasyev9a989702012-06-29 17:44:00 -070070 }
71 else
72 {
Alexander Afanasyev78057c32012-07-06 15:18:46 -070073 return std::make_pair (s_iterator_to (item.first), false);
Alexander Afanasyev9a989702012-06-29 17:44:00 -070074 }
75
76 return item;
77 }
78
79 inline void
Alexander Afanasyev78057c32012-07-06 15:18:46 -070080 erase (const FullKey &key)
81 {
82 iterator foundItem, lastItem;
83 bool reachLast;
84 boost::tie (foundItem, reachLast, lastItem) = trie_.find (key);
Alexander Afanasyeveec66292013-02-06 16:23:21 -080085
Alexander Afanasyev78057c32012-07-06 15:18:46 -070086 if (!reachLast || lastItem->payload () == PayloadTraits::empty_payload)
87 return; // nothing to invalidate
88
89 erase (lastItem);
90 }
91
92 inline void
Alexander Afanasyev9a989702012-06-29 17:44:00 -070093 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
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700101 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 }
Alexander Afanasyevadcccf42012-11-26 23:55:34 -0800119
120 /**
121 * @brief Find a node that has the exact match with the key
122 */
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);
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800129
Alexander Afanasyevadcccf42012-11-26 23:55:34 -0800130 if (!reachLast || lastItem->payload () == PayloadTraits::empty_payload)
131 return end ();
132
133 return lastItem;
134 }
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800135
Alexander Afanasyev9a989702012-06-29 17:44:00 -0700136 /**
137 * @brief Find a node that has the longest common prefix with key (FIB/PIT lookup)
138 */
139 inline iterator
140 longest_prefix_match (const FullKey &key)
141 {
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700142 iterator foundItem, lastItem;
143 bool reachLast;
144 boost::tie (foundItem, reachLast, lastItem) = trie_.find (key);
145 if (foundItem != trie_.end ())
Alexander Afanasyev9a989702012-06-29 17:44:00 -0700146 {
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700147 policy_.lookup (s_iterator_to (foundItem));
Alexander Afanasyev9a989702012-06-29 17:44:00 -0700148 }
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700149 return foundItem;
Alexander Afanasyev9a989702012-06-29 17:44:00 -0700150 }
151
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800152 /**
153 * @brief Find a node that has the longest common prefix with key (FIB/PIT lookup)
154 */
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
Alexander Afanasyev30f60e32012-07-10 14:21:16 -0700169 // /**
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
Alexander Afanasyev9a989702012-06-29 17:44:00 -0700179 /**
180 * @brief Find a node that has prefix at least as the key (cache lookup)
181 */
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 ();
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800192
Alexander Afanasyev9a989702012-06-29 17:44:00 -0700193 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
208 /**
209 * @brief Find a node that has prefix at least as the key
210 */
211 template<class Predicate>
212 inline iterator
Alexander Afanasyeveec89ba2013-07-19 16:34:30 -0700213 deepest_prefix_match_if (const FullKey &key, Predicate pred)
Alexander Afanasyev9a989702012-06-29 17:44:00 -0700214 {
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 ();
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800222
Alexander Afanasyev9a989702012-06-29 17:44:00 -0700223 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 }
Alexander Afanasyev9a989702012-06-29 17:44:00 -0700238
Alexander Afanasyeveec89ba2013-07-19 16:34:30 -0700239 /**
240 * @brief Find a node that has prefix at least as the key
241 *
242 * This version of find checks predicate for the next level and if
243 * predicate is True, returns first deepest match available
244 */
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
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700273 iterator end () const
Alexander Afanasyev9a989702012-06-29 17:44:00 -0700274 {
275 return 0;
276 }
277
278 const parent_trie &
279 getTrie () const { return trie_; }
280
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700281 parent_trie &
282 getTrie () { return trie_; }
283
Alexander Afanasyev9e96e362012-07-02 23:04:39 -0700284 const policy_container &
Alexander Afanasyev9a989702012-06-29 17:44:00 -0700285 getPolicy () const { return policy_; }
286
Alexander Afanasyev9e96e362012-07-02 23:04:39 -0700287 policy_container &
Alexander Afanasyev9a989702012-06-29 17:44:00 -0700288 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 }
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800298
Alexander Afanasyev9a989702012-06-29 17:44:00 -0700299private:
300 parent_trie trie_;
Alexander Afanasyev30f60e32012-07-10 14:21:16 -0700301 mutable policy_container policy_;
Alexander Afanasyev9a989702012-06-29 17:44:00 -0700302};
303
Alexander Afanasyev30cb1172012-07-06 10:47:39 -0700304} // ndnSIM
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700305} // ndn
Alexander Afanasyeve77db792012-08-09 11:10:58 -0700306} // ns3
Alexander Afanasyev9a989702012-06-29 17:44:00 -0700307
308#endif // TRIE_WITH_POLICY_H_