blob: d6b00b3b9a51f88bd042454bf1193e994e64491a [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 Afanasyevbe55cf62014-12-20 17:51:09 -080030template<typename FullKey, typename PayloadTraits, typename PolicyTraits>
31class trie_with_policy {
Alexander Afanasyev9a989702012-06-29 17:44:00 -070032public:
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080033 typedef trie<FullKey, PayloadTraits, typename PolicyTraits::policy_hook_type> parent_trie;
Alexander Afanasyev9e96e362012-07-02 23:04:39 -070034
35 typedef typename parent_trie::iterator iterator;
Alexander Afanasyev1ba09b82012-07-09 09:16:14 -070036 typedef typename parent_trie::const_iterator const_iterator;
Alexander Afanasyev9e96e362012-07-02 23:04:39 -070037
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080038 typedef typename PolicyTraits::
39 template policy<trie_with_policy<FullKey, PayloadTraits, PolicyTraits>, parent_trie,
40 typename PolicyTraits::template container_hook<parent_trie>::type>::type
41 policy_container;
Alexander Afanasyev9a989702012-06-29 17:44:00 -070042
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080043 inline trie_with_policy(size_t bucketSize = 1, size_t bucketIncrement = 1)
44 : trie_(name::Component(), bucketSize, bucketIncrement)
45 , policy_(*this)
Alexander Afanasyev9a989702012-06-29 17:44:00 -070046 {
47 }
48
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080049 inline std::pair<iterator, bool>
50 insert(const FullKey& key, typename PayloadTraits::insert_type payload)
Alexander Afanasyev9a989702012-06-29 17:44:00 -070051 {
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080052 std::pair<iterator, bool> item = trie_.insert(key, payload);
Alexander Afanasyev9a989702012-06-29 17:44:00 -070053
54 if (item.second) // real insert
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080055 {
56 bool ok = policy_.insert(s_iterator_to(item.first));
57 if (!ok) {
58 item.first->erase(); // cannot insert
59 return std::make_pair(end(), false);
Alexander Afanasyev9a989702012-06-29 17:44:00 -070060 }
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080061 }
62 else {
63 return std::make_pair(s_iterator_to(item.first), false);
64 }
Alexander Afanasyev9a989702012-06-29 17:44:00 -070065
66 return item;
67 }
68
69 inline void
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080070 erase(const FullKey& key)
Alexander Afanasyev78057c32012-07-06 15:18:46 -070071 {
72 iterator foundItem, lastItem;
73 bool reachLast;
Alexander Afanasyev07179012014-12-21 00:23:04 -080074 std::tie(foundItem, reachLast, lastItem) = trie_.find(key);
Alexander Afanasyeveec66292013-02-06 16:23:21 -080075
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080076 if (!reachLast || lastItem->payload() == PayloadTraits::empty_payload)
Alexander Afanasyev78057c32012-07-06 15:18:46 -070077 return; // nothing to invalidate
78
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080079 erase(lastItem);
Alexander Afanasyev78057c32012-07-06 15:18:46 -070080 }
81
82 inline void
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080083 erase(iterator node)
Alexander Afanasyev9a989702012-06-29 17:44:00 -070084 {
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080085 if (node == end())
86 return;
Alexander Afanasyev9a989702012-06-29 17:44:00 -070087
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080088 policy_.erase(s_iterator_to(node));
89 node->erase(); // will do cleanup here
Alexander Afanasyev9a989702012-06-29 17:44:00 -070090 }
91
Alexander Afanasyev78057c32012-07-06 15:18:46 -070092 inline void
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080093 clear()
Alexander Afanasyev78057c32012-07-06 15:18:46 -070094 {
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080095 policy_.clear();
96 trie_.clear();
Alexander Afanasyev78057c32012-07-06 15:18:46 -070097 }
98
99 template<typename Modifier>
100 bool
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800101 modify(iterator position, Modifier mod)
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700102 {
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800103 if (position == end())
104 return false;
105 if (position->payload() == PayloadTraits::empty_payload)
106 return false;
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700107
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800108 mod(*position->payload());
109 policy_.update(position);
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700110 return true;
111 }
Alexander Afanasyevadcccf42012-11-26 23:55:34 -0800112
113 /**
114 * @brief Find a node that has the exact match with the key
115 */
116 inline iterator
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800117 find_exact(const FullKey& key)
Alexander Afanasyevadcccf42012-11-26 23:55:34 -0800118 {
119 iterator foundItem, lastItem;
120 bool reachLast;
Alexander Afanasyev07179012014-12-21 00:23:04 -0800121 std::tie(foundItem, reachLast, lastItem) = trie_.find(key);
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800122
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800123 if (!reachLast || lastItem->payload() == PayloadTraits::empty_payload)
124 return end();
Alexander Afanasyevadcccf42012-11-26 23:55:34 -0800125
126 return lastItem;
127 }
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800128
Alexander Afanasyev9a989702012-06-29 17:44:00 -0700129 /**
130 * @brief Find a node that has the longest common prefix with key (FIB/PIT lookup)
131 */
132 inline iterator
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800133 longest_prefix_match(const FullKey& key)
Alexander Afanasyev9a989702012-06-29 17:44:00 -0700134 {
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700135 iterator foundItem, lastItem;
136 bool reachLast;
Alexander Afanasyev07179012014-12-21 00:23:04 -0800137 std::tie(foundItem, reachLast, lastItem) = trie_.find(key);
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800138 if (foundItem != trie_.end()) {
139 policy_.lookup(s_iterator_to(foundItem));
140 }
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700141 return foundItem;
Alexander Afanasyev9a989702012-06-29 17:44:00 -0700142 }
143
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800144 /**
145 * @brief Find a node that has the longest common prefix with key (FIB/PIT lookup)
146 */
147 template<class Predicate>
148 inline iterator
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800149 longest_prefix_match_if(const FullKey& key, Predicate pred)
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800150 {
151 iterator foundItem, lastItem;
152 bool reachLast;
Alexander Afanasyev07179012014-12-21 00:23:04 -0800153 std::tie(foundItem, reachLast, lastItem) = trie_.find_if(key, pred);
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800154 if (foundItem != trie_.end()) {
155 policy_.lookup(s_iterator_to(foundItem));
156 }
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800157 return foundItem;
158 }
159
Alexander Afanasyev30f60e32012-07-10 14:21:16 -0700160 // /**
161 // * @brief Const version of the longest common prefix match
162 // * (semi-const, because there could be update of the policy anyways)
163 // */
164 // inline const_iterator
165 // longest_prefix_match (const FullKey &key) const
166 // {
167 // return static_cast<trie_with_policy*> (this)->longest_prefix_match (key);
168 // }
169
Alexander Afanasyev9a989702012-06-29 17:44:00 -0700170 /**
171 * @brief Find a node that has prefix at least as the key (cache lookup)
172 */
173 inline iterator
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800174 deepest_prefix_match(const FullKey& key)
Alexander Afanasyev9a989702012-06-29 17:44:00 -0700175 {
176 iterator foundItem, lastItem;
177 bool reachLast;
Alexander Afanasyev07179012014-12-21 00:23:04 -0800178 std::tie(foundItem, reachLast, lastItem) = trie_.find(key);
Alexander Afanasyev9a989702012-06-29 17:44:00 -0700179
180 // guard in case we don't have anything in the trie
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800181 if (lastItem == trie_.end())
182 return trie_.end();
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800183
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800184 if (reachLast) {
185 if (foundItem == trie_.end()) {
186 foundItem = lastItem->find(); // should be something
Alexander Afanasyev9a989702012-06-29 17:44:00 -0700187 }
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800188 policy_.lookup(s_iterator_to(foundItem));
189 return foundItem;
190 }
191 else { // couldn't find a node that has prefix at least as key
192 return trie_.end();
193 }
Alexander Afanasyev9a989702012-06-29 17:44:00 -0700194 }
195
196 /**
197 * @brief Find a node that has prefix at least as the key
198 */
199 template<class Predicate>
200 inline iterator
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800201 deepest_prefix_match_if(const FullKey& key, Predicate pred)
Alexander Afanasyev9a989702012-06-29 17:44:00 -0700202 {
203 iterator foundItem, lastItem;
204 bool reachLast;
Alexander Afanasyev07179012014-12-21 00:23:04 -0800205 std::tie(foundItem, reachLast, lastItem) = trie_.find(key);
Alexander Afanasyev9a989702012-06-29 17:44:00 -0700206
207 // guard in case we don't have anything in the trie
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800208 if (lastItem == trie_.end())
209 return trie_.end();
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800210
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800211 if (reachLast) {
212 foundItem = lastItem->find_if(pred); // may or may not find something
213 if (foundItem == trie_.end()) {
214 return trie_.end();
Alexander Afanasyev9a989702012-06-29 17:44:00 -0700215 }
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800216 policy_.lookup(s_iterator_to(foundItem));
217 return foundItem;
218 }
219 else { // couldn't find a node that has prefix at least as key
220 return trie_.end();
221 }
Alexander Afanasyev9a989702012-06-29 17:44:00 -0700222 }
Alexander Afanasyev9a989702012-06-29 17:44:00 -0700223
Alexander Afanasyeveec89ba2013-07-19 16:34:30 -0700224 /**
225 * @brief Find a node that has prefix at least as the key
226 *
227 * This version of find checks predicate for the next level and if
228 * predicate is True, returns first deepest match available
229 */
230 template<class Predicate>
231 inline iterator
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800232 deepest_prefix_match_if_next_level(const FullKey& key, Predicate pred)
Alexander Afanasyeveec89ba2013-07-19 16:34:30 -0700233 {
234 iterator foundItem, lastItem;
235 bool reachLast;
Alexander Afanasyev07179012014-12-21 00:23:04 -0800236 std::tie(foundItem, reachLast, lastItem) = trie_.find(key);
Alexander Afanasyeveec89ba2013-07-19 16:34:30 -0700237
238 // guard in case we don't have anything in the trie
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800239 if (lastItem == trie_.end())
240 return trie_.end();
Alexander Afanasyeveec89ba2013-07-19 16:34:30 -0700241
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800242 if (reachLast) {
243 foundItem = lastItem->find_if_next_level(pred); // may or may not find something
244 if (foundItem == trie_.end()) {
245 return trie_.end();
Alexander Afanasyeveec89ba2013-07-19 16:34:30 -0700246 }
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800247 policy_.lookup(s_iterator_to(foundItem));
248 return foundItem;
249 }
250 else { // couldn't find a node that has prefix at least as key
251 return trie_.end();
252 }
Alexander Afanasyeveec89ba2013-07-19 16:34:30 -0700253 }
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800254
255 iterator
256 end() const
Alexander Afanasyev9a989702012-06-29 17:44:00 -0700257 {
258 return 0;
259 }
260
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800261 const parent_trie&
262 getTrie() const
263 {
264 return trie_;
265 }
Alexander Afanasyev9a989702012-06-29 17:44:00 -0700266
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800267 parent_trie&
268 getTrie()
269 {
270 return trie_;
271 }
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700272
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800273 const policy_container&
274 getPolicy() const
275 {
276 return policy_;
277 }
Alexander Afanasyev9a989702012-06-29 17:44:00 -0700278
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800279 policy_container&
280 getPolicy()
281 {
282 return policy_;
283 }
Alexander Afanasyev9a989702012-06-29 17:44:00 -0700284
285 static inline iterator
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800286 s_iterator_to(typename parent_trie::iterator item)
Alexander Afanasyev9a989702012-06-29 17:44:00 -0700287 {
288 if (item == 0)
289 return 0;
290 else
291 return &(*item);
292 }
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800293
Alexander Afanasyev9a989702012-06-29 17:44:00 -0700294private:
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800295 parent_trie trie_;
Alexander Afanasyev30f60e32012-07-10 14:21:16 -0700296 mutable policy_container policy_;
Alexander Afanasyev9a989702012-06-29 17:44:00 -0700297};
298
Alexander Afanasyev30cb1172012-07-06 10:47:39 -0700299} // ndnSIM
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700300} // ndn
Alexander Afanasyeve77db792012-08-09 11:10:58 -0700301} // ns3
Alexander Afanasyev9a989702012-06-29 17:44:00 -0700302
303#endif // TRIE_WITH_POLICY_H_