blob: 28c075e4070c727458fe8d9f574cf89e0d320075 [file] [log] [blame]
Alexander Afanasyev60a7b622014-12-20 17:04:07 -08001/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2/**
3 * Copyright (c) 2011-2015 Regents of the University of California.
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -07004 *
Alexander Afanasyev60a7b622014-12-20 17:04:07 -08005 * This file is part of ndnSIM. See AUTHORS for complete list of ndnSIM authors and
6 * contributors.
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -07007 *
Alexander Afanasyev60a7b622014-12-20 17:04:07 -08008 * ndnSIM is free software: you can redistribute it and/or modify it under the terms
9 * of the GNU General Public License as published by the Free Software Foundation,
10 * either version 3 of the License, or (at your option) any later version.
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -070011 *
Alexander Afanasyev60a7b622014-12-20 17:04:07 -080012 * ndnSIM is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
13 * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
14 * PURPOSE. See the GNU General Public License for more details.
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -070015 *
Alexander Afanasyev60a7b622014-12-20 17:04:07 -080016 * You should have received a copy of the GNU General Public License along with
17 * ndnSIM, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
18 **/
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -070019
Alexander Afanasyev9a989702012-06-29 17:44:00 -070020#ifndef TRIE_H_
21#define TRIE_H_
22
Spyridon Mastorakis460f57c2014-12-17 00:44:14 -080023/// @cond include_hidden
24
Spyridon Mastorakis53e922f2014-10-17 17:29:26 -070025#include "ns3/ndnSIM/model/ndn-common.hpp"
26
Alexander Afanasyev9a989702012-06-29 17:44:00 -070027#include "ns3/ptr.h"
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -070028
29#include <boost/intrusive/unordered_set.hpp>
Alexander Afanasyev89fb5352012-06-12 22:43:16 -070030#include <boost/intrusive/list.hpp>
Alexander Afanasyev9a989702012-06-29 17:44:00 -070031#include <boost/intrusive/set.hpp>
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -070032#include <boost/functional/hash.hpp>
Alexander Afanasyev89fb5352012-06-12 22:43:16 -070033#include <boost/interprocess/smart_ptr/unique_ptr.hpp>
Alexander Afanasyev07179012014-12-21 00:23:04 -080034#include <tuple>
Alexander Afanasyev78057c32012-07-06 15:18:46 -070035#include <boost/foreach.hpp>
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -070036#include <boost/mpl/if.hpp>
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -070037
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070038namespace ns3 {
39namespace ndn {
40namespace ndnSIM {
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -070041
42/////////////////////////////////////////////////////
43// Allow customization for payload
44//
Alexander Afanasyev8566f452012-12-10 15:21:51 -080045template<typename Payload, typename BasePayload = Payload>
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080046struct pointer_payload_traits {
47 typedef Payload payload_type; // general type of the payload
48 typedef Payload* storage_type; // how the payload is actually stored
49 typedef Payload* insert_type; // what parameter is inserted
Alexander Afanasyev0845c092012-07-13 17:45:33 -070050
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080051 typedef Payload* return_type; // what is returned on access
52 typedef const Payload* const_return_type; // what is returned on const access
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -070053
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080054 typedef BasePayload*
55 base_type; // base type of the entry (when implementation details need to be hidden)
56 typedef const BasePayload*
57 const_base_type; // const base type of the entry (when implementation details need to be hidden)
Alexander Afanasyeveec66292013-02-06 16:23:21 -080058
Alexander Afanasyev78057c32012-07-06 15:18:46 -070059 static Payload* empty_payload;
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -070060};
61
Alexander Afanasyev8566f452012-12-10 15:21:51 -080062template<typename Payload, typename BasePayload>
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080063Payload* pointer_payload_traits<Payload, BasePayload>::empty_payload = 0;
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -070064
Alexander Afanasyev8566f452012-12-10 15:21:51 -080065template<typename Payload, typename BasePayload = Payload>
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080066struct smart_pointer_payload_traits {
67 typedef Payload payload_type;
68 typedef ns3::Ptr<Payload> storage_type;
69 typedef ns3::Ptr<Payload> insert_type;
Alexander Afanasyeveec66292013-02-06 16:23:21 -080070
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080071 typedef ns3::Ptr<Payload> return_type;
Alexander Afanasyev0845c092012-07-13 17:45:33 -070072 typedef ns3::Ptr<const Payload> const_return_type;
Alexander Afanasyev8566f452012-12-10 15:21:51 -080073
74 typedef ns3::Ptr<BasePayload> base_type;
75 typedef ns3::Ptr<const BasePayload> const_base_type;
Alexander Afanasyeveec66292013-02-06 16:23:21 -080076
Alexander Afanasyev78057c32012-07-06 15:18:46 -070077 static ns3::Ptr<Payload> empty_payload;
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -070078};
79
Alexander Afanasyev8566f452012-12-10 15:21:51 -080080template<typename Payload, typename BasePayload>
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080081ns3::Ptr<Payload> smart_pointer_payload_traits<Payload, BasePayload>::empty_payload = 0;
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -070082
Alexander Afanasyev8566f452012-12-10 15:21:51 -080083template<typename Payload, typename BasePayload = Payload>
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080084struct non_pointer_traits {
85 typedef Payload payload_type;
86 typedef Payload storage_type;
87 typedef const Payload& insert_type; // nothing to insert
Alexander Afanasyev0845c092012-07-13 17:45:33 -070088
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080089 typedef Payload& return_type;
90 typedef const Payload& const_return_type;
Alexander Afanasyeveec66292013-02-06 16:23:21 -080091
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080092 typedef BasePayload& base_type;
Alexander Afanasyev62304f22012-12-10 18:06:21 -080093 typedef const BasePayload& const_base_type;
Alexander Afanasyeveec66292013-02-06 16:23:21 -080094
Alexander Afanasyev0845c092012-07-13 17:45:33 -070095 static Payload empty_payload;
96};
97
Alexander Afanasyev8566f452012-12-10 15:21:51 -080098template<typename Payload, typename BasePayload>
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080099Payload non_pointer_traits<Payload, BasePayload>::empty_payload = Payload();
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700100
101////////////////////////////////////////////////////
102// forward declarations
103//
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800104template<typename FullKey, typename PayloadTraits, typename PolicyHook>
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800105class trie;
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700106
Alexander Afanasyev30f60e32012-07-10 14:21:16 -0700107template<typename FullKey, typename PayloadTraits, typename PolicyHook>
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700108inline std::ostream&
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800109operator<<(std::ostream& os, const trie<FullKey, PayloadTraits, PolicyHook>& trie_node);
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700110
Alexander Afanasyev30f60e32012-07-10 14:21:16 -0700111template<typename FullKey, typename PayloadTraits, typename PolicyHook>
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700112bool
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800113operator==(const trie<FullKey, PayloadTraits, PolicyHook>& a,
114 const trie<FullKey, PayloadTraits, PolicyHook>& b);
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700115
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800116template<typename FullKey, typename PayloadTraits, typename PolicyHook>
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700117std::size_t
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800118hash_value(const trie<FullKey, PayloadTraits, PolicyHook>& trie_node);
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700119
120///////////////////////////////////////////////////
121// actual definition
122//
Alexander Afanasyev1cb4aad2012-08-09 14:58:16 -0700123template<class T, class NonConstT>
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700124class trie_iterator;
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700125
Alexander Afanasyev0845c092012-07-13 17:45:33 -0700126template<class T>
127class trie_point_iterator;
128
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800129template<typename FullKey, typename PayloadTraits, typename PolicyHook>
130class trie {
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700131public:
Spyridon Mastorakis1f1cd5e2014-12-04 11:12:40 -0800132 typedef typename FullKey::value_type Key;
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700133
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800134 typedef trie* iterator;
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700135 typedef const trie* const_iterator;
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700136
Alexander Afanasyev1cb4aad2012-08-09 14:58:16 -0700137 typedef trie_iterator<trie, trie> recursive_iterator;
138 typedef trie_iterator<const trie, trie> const_recursive_iterator;
Alexander Afanasyev30f60e32012-07-10 14:21:16 -0700139
Alexander Afanasyev0845c092012-07-13 17:45:33 -0700140 typedef trie_point_iterator<trie> point_iterator;
141 typedef trie_point_iterator<const trie> const_point_iterator;
142
Alexander Afanasyev30f60e32012-07-10 14:21:16 -0700143 typedef PayloadTraits payload_traits;
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800144
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800145 inline trie(const Key& key, size_t bucketSize = 1, size_t bucketIncrement = 1)
146 : key_(key)
147 , initialBucketSize_(bucketSize)
148 , bucketIncrement_(bucketIncrement)
149 , bucketSize_(initialBucketSize_)
150 , buckets_(new bucket_type[bucketSize_]) // cannot use normal pointer, because lifetime of
151 // buckets should be larger than lifetime of the
152 // container
153 , children_(bucket_traits(buckets_.get(), bucketSize_))
154 , payload_(PayloadTraits::empty_payload)
155 , parent_(0)
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700156 {
157 }
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700158
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800159 inline ~trie()
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700160 {
161 payload_ = PayloadTraits::empty_payload; // necessary for smart pointers...
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800162 children_.clear_and_dispose(trie_delete_disposer());
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700163 }
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700164
165 void
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800166 clear()
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700167 {
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800168 children_.clear_and_dispose(trie_delete_disposer());
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700169 }
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700170
171 template<class Predicate>
172 void
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800173 clear_if(Predicate cond)
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700174 {
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800175 recursive_iterator trieNode(this);
176 recursive_iterator end(0);
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700177
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800178 while (trieNode != end) {
179 if (cond(*trieNode)) {
180 trieNode = recursive_iterator(trieNode->erase());
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700181 }
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800182 trieNode++;
183 }
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700184 }
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800185
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700186 // actual entry
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800187 friend bool operator==<>(const trie<FullKey, PayloadTraits, PolicyHook>& a,
188 const trie<FullKey, PayloadTraits, PolicyHook>& b);
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700189
190 friend std::size_t
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800191 hash_value<>(const trie<FullKey, PayloadTraits, PolicyHook>& trie_node);
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700192
193 inline std::pair<iterator, bool>
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800194 insert(const FullKey& key, typename PayloadTraits::insert_type payload)
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700195 {
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800196 trie* trieNode = this;
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800197
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800198 BOOST_FOREACH (const Key& subkey, key) {
199 typename unordered_set::iterator item = trieNode->children_.find(subkey);
200 if (item == trieNode->children_.end()) {
201 trie* newNode = new trie(subkey, initialBucketSize_, bucketIncrement_);
202 // std::cout << "new " << newNode << "\n";
203 newNode->parent_ = trieNode;
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700204
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800205 if (trieNode->children_.size() >= trieNode->bucketSize_) {
206 trieNode->bucketSize_ += trieNode->bucketIncrement_;
207 trieNode->bucketIncrement_ *= 2; // increase bucketIncrement exponentially
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800208
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800209 buckets_array newBuckets(new bucket_type[trieNode->bucketSize_]);
210 trieNode->children_.rehash(bucket_traits(newBuckets.get(), trieNode->bucketSize_));
211 trieNode->buckets_.swap(newBuckets);
212 }
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800213
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800214 std::pair<typename unordered_set::iterator, bool> ret =
215 trieNode->children_.insert(*newNode);
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800216
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800217 trieNode = &(*ret.first);
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700218 }
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800219 else
220 trieNode = &(*item);
221 }
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700222
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800223 if (trieNode->payload_ == PayloadTraits::empty_payload) {
224 trieNode->payload_ = payload;
225 return std::make_pair(trieNode, true);
226 }
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700227 else
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800228 return std::make_pair(trieNode, false);
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700229 }
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700230
231 /**
232 * @brief Removes payload (if it exists) and if there are no children, prunes parents trie
233 */
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700234 inline iterator
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800235 erase()
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700236 {
237 payload_ = PayloadTraits::empty_payload;
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800238 return prune();
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700239 }
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700240
241 /**
242 * @brief Do exactly as erase, but without erasing the payload
243 */
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700244 inline iterator
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800245 prune()
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700246 {
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800247 if (payload_ == PayloadTraits::empty_payload && children_.size() == 0) {
248 if (parent_ == 0)
249 return this;
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700250
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800251 trie* parent = parent_;
252 parent->children_
253 .erase_and_dispose(*this,
254 trie_delete_disposer()); // delete this; basically, committing a suicide
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700255
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800256 return parent->prune();
257 }
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700258 return this;
259 }
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700260
Alexander Afanasyev70426a02012-08-15 15:39:18 -0700261 /**
262 * @brief Perform prune of the node, but without attempting to parent of the node
263 */
264 inline void
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800265 prune_node()
Alexander Afanasyev70426a02012-08-15 15:39:18 -0700266 {
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800267 if (payload_ == PayloadTraits::empty_payload && children_.size() == 0) {
268 if (parent_ == 0)
269 return;
Alexander Afanasyev70426a02012-08-15 15:39:18 -0700270
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800271 trie* parent = parent_;
272 parent->children_
273 .erase_and_dispose(*this,
274 trie_delete_disposer()); // delete this; basically, committing a suicide
275 }
Alexander Afanasyev70426a02012-08-15 15:39:18 -0700276 }
277
Alexander Afanasyev07179012014-12-21 00:23:04 -0800278 // inline std::tuple<const iterator, bool, const iterator>
Alexander Afanasyev30f60e32012-07-10 14:21:16 -0700279 // find (const FullKey &key) const
280 // {
281 // return const_cast<trie*> (this)->find (key);
282 // }
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700283
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700284 /**
285 * @brief Perform the longest prefix match
286 * @param key the key for which to perform the longest prefix match
287 *
288 * @return ->second is true if prefix in ->first is longer than key
289 */
Alexander Afanasyev07179012014-12-21 00:23:04 -0800290 inline std::tuple<iterator, bool, iterator>
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800291 find(const FullKey& key)
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700292 {
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800293 trie* trieNode = this;
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700294 iterator foundNode = (payload_ != PayloadTraits::empty_payload) ? this : 0;
295 bool reachLast = true;
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800296
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800297 BOOST_FOREACH (const Key& subkey, key) {
298 typename unordered_set::iterator item = trieNode->children_.find(subkey);
299 if (item == trieNode->children_.end()) {
300 reachLast = false;
301 break;
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700302 }
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800303 else {
304 trieNode = &(*item);
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700305
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800306 if (trieNode->payload_ != PayloadTraits::empty_payload)
307 foundNode = trieNode;
308 }
309 }
310
Alexander Afanasyev07179012014-12-21 00:23:04 -0800311 return std::make_tuple(foundNode, reachLast, trieNode);
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800312 }
313
314 /**
315 * @brief Perform the longest prefix match satisfying preficate
316 * @param key the key for which to perform the longest prefix match
317 *
318 * @return ->second is true if prefix in ->first is longer than key
319 */
320 template<class Predicate>
Alexander Afanasyev07179012014-12-21 00:23:04 -0800321 inline std::tuple<iterator, bool, iterator>
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800322 find_if(const FullKey& key, Predicate pred)
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800323 {
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800324 trie* trieNode = this;
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800325 iterator foundNode = (payload_ != PayloadTraits::empty_payload) ? this : 0;
326 bool reachLast = true;
327
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800328 BOOST_FOREACH (const Key& subkey, key) {
329 typename unordered_set::iterator item = trieNode->children_.find(subkey);
330 if (item == trieNode->children_.end()) {
331 reachLast = false;
332 break;
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800333 }
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800334 else {
335 trieNode = &(*item);
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800336
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800337 if (trieNode->payload_ != PayloadTraits::empty_payload && pred(trieNode->payload_)) {
338 foundNode = trieNode;
339 }
340 }
341 }
342
Alexander Afanasyev07179012014-12-21 00:23:04 -0800343 return std::make_tuple(foundNode, reachLast, trieNode);
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700344 }
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700345
346 /**
347 * @brief Find next payload of the sub-trie
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800348 * @returns end() or a valid iterator pointing to the trie leaf (order is not defined, enumeration
349 * )
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700350 */
351 inline iterator
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800352 find()
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700353 {
354 if (payload_ != PayloadTraits::empty_payload)
355 return this;
356
Alexander Afanasyev30f60e32012-07-10 14:21:16 -0700357 typedef trie<FullKey, PayloadTraits, PolicyHook> trie;
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800358 for (typename trie::unordered_set::iterator subnode = children_.begin();
359 subnode != children_.end(); subnode++)
360 // BOOST_FOREACH (trie &subnode, children_)
361 {
362 iterator value = subnode->find();
363 if (value != 0)
364 return value;
365 }
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800366
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700367 return 0;
368 }
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700369
370 /**
371 * @brief Find next payload of the sub-trie satisfying the predicate
372 * @param pred predicate
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800373 * @returns end() or a valid iterator pointing to the trie leaf (order is not defined, enumeration
374 * )
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700375 */
376 template<class Predicate>
Alexander Afanasyev30f60e32012-07-10 14:21:16 -0700377 inline const iterator
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800378 find_if(Predicate pred)
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700379 {
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800380 if (payload_ != PayloadTraits::empty_payload && pred(payload_))
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700381 return this;
382
Alexander Afanasyev30f60e32012-07-10 14:21:16 -0700383 typedef trie<FullKey, PayloadTraits, PolicyHook> trie;
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800384 for (typename trie::unordered_set::iterator subnode = children_.begin();
385 subnode != children_.end(); subnode++)
386 // BOOST_FOREACH (const trie &subnode, children_)
387 {
388 iterator value = subnode->find_if(pred);
389 if (value != 0)
390 return value;
391 }
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800392
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700393 return 0;
394 }
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700395
Alexander Afanasyeveec89ba2013-07-19 16:34:30 -0700396 /**
397 * @brief Find next payload of the sub-trie satisfying the predicate
398 * @param pred predicate
399 *
400 * This version check predicate only for the next level children
401 *
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800402 * @returns end() or a valid iterator pointing to the trie leaf (order is not defined, enumeration
403 *)
Alexander Afanasyeveec89ba2013-07-19 16:34:30 -0700404 */
405 template<class Predicate>
406 inline const iterator
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800407 find_if_next_level(Predicate pred)
Alexander Afanasyeveec89ba2013-07-19 16:34:30 -0700408 {
409 typedef trie<FullKey, PayloadTraits, PolicyHook> trie;
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800410 for (typename trie::unordered_set::iterator subnode = children_.begin();
411 subnode != children_.end(); subnode++) {
412 if (pred(subnode->key())) {
413 return subnode->find();
Alexander Afanasyeveec89ba2013-07-19 16:34:30 -0700414 }
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800415 }
Alexander Afanasyeveec89ba2013-07-19 16:34:30 -0700416
417 return 0;
418 }
419
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800420 iterator
421 end()
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700422 {
423 return 0;
424 }
425
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800426 const_iterator
427 end() const
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700428 {
429 return 0;
430 }
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700431
Alexander Afanasyev0845c092012-07-13 17:45:33 -0700432 typename PayloadTraits::const_return_type
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800433 payload() const
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700434 {
435 return payload_;
436 }
437
Alexander Afanasyev0845c092012-07-13 17:45:33 -0700438 typename PayloadTraits::return_type
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800439 payload()
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700440 {
441 return payload_;
442 }
443
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700444 void
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800445 set_payload(typename PayloadTraits::insert_type payload)
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700446 {
447 payload_ = payload;
448 }
Alexander Afanasyev0560eec2012-07-16 15:44:31 -0700449
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800450 Key
451 key() const
Alexander Afanasyev0560eec2012-07-16 15:44:31 -0700452 {
453 return key_;
454 }
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800455
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700456 inline void
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800457 PrintStat(std::ostream& os) const;
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800458
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700459private:
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800460 // The disposer object function
461 struct trie_delete_disposer {
462 void
463 operator()(trie* delete_this)
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700464 {
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700465 delete delete_this;
466 }
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700467 };
468
469 template<class D>
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800470 struct array_disposer {
471 void
472 operator()(D* array)
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700473 {
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800474 delete[] array;
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700475 }
476 };
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700477
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800478 friend std::ostream& operator<<<>(std::ostream& os, const trie& trie_node);
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700479
480public:
481 PolicyHook policy_hook_;
482
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700483private:
Alexander Afanasyev30cb1172012-07-06 10:47:39 -0700484 boost::intrusive::unordered_set_member_hook<> unordered_set_member_hook_;
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700485
486 // necessary typedefs
487 typedef trie self_type;
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800488 typedef boost::intrusive::member_hook<trie, boost::intrusive::unordered_set_member_hook<>,
489 &trie::unordered_set_member_hook_> member_hook;
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700490
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800491 typedef boost::intrusive::unordered_set<trie, member_hook> unordered_set;
492 typedef typename unordered_set::bucket_type bucket_type;
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700493 typedef typename unordered_set::bucket_traits bucket_traits;
494
Alexander Afanasyev1cb4aad2012-08-09 14:58:16 -0700495 template<class T, class NonConstT>
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700496 friend class trie_iterator;
Alexander Afanasyev0845c092012-07-13 17:45:33 -0700497
498 template<class T>
499 friend class trie_point_iterator;
500
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700501 ////////////////////////////////////////////////
502 // Actual data
503 ////////////////////////////////////////////////
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800504
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700505 Key key_; ///< name component
506
507 size_t initialBucketSize_;
508 size_t bucketIncrement_;
509
510 size_t bucketSize_;
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800511 typedef boost::interprocess::unique_ptr<bucket_type, array_disposer<bucket_type>> buckets_array;
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700512 buckets_array buckets_;
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700513 unordered_set children_;
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800514
Alexander Afanasyev0845c092012-07-13 17:45:33 -0700515 typename PayloadTraits::storage_type payload_;
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800516 trie* parent_; // to make cleaning effective
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700517};
518
Alexander Afanasyev30f60e32012-07-10 14:21:16 -0700519template<typename FullKey, typename PayloadTraits, typename PolicyHook>
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700520inline std::ostream&
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800521operator<<(std::ostream& os, const trie<FullKey, PayloadTraits, PolicyHook>& trie_node)
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700522{
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800523 os << "# " << trie_node.key_ << ((trie_node.payload_ != PayloadTraits::empty_payload) ? "*" : "")
524 << std::endl;
Alexander Afanasyev30f60e32012-07-10 14:21:16 -0700525 typedef trie<FullKey, PayloadTraits, PolicyHook> trie;
Alexander Afanasyev051d3782012-07-03 10:10:15 -0700526
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800527 for (typename trie::unordered_set::const_iterator subnode = trie_node.children_.begin();
528 subnode != trie_node.children_.end(); subnode++)
Alexander Afanasyev051d3782012-07-03 10:10:15 -0700529 // BOOST_FOREACH (const trie &subnode, trie_node.children_)
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800530 {
531 os << "\"" << &trie_node << "\""
532 << " [label=\"" << trie_node.key_
533 << ((trie_node.payload_ != PayloadTraits::empty_payload) ? "*" : "") << "\"]\n";
534 os << "\"" << &(*subnode) << "\""
535 << " [label=\"" << subnode->key_
536 << ((subnode->payload_ != PayloadTraits::empty_payload) ? "*" : "") << "\"]"
537 "\n";
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800538
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800539 os << "\"" << &trie_node << "\""
540 << " -> "
541 << "\"" << &(*subnode) << "\""
542 << "\n";
543 os << *subnode;
544 }
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700545
546 return os;
547}
548
Alexander Afanasyev30f60e32012-07-10 14:21:16 -0700549template<typename FullKey, typename PayloadTraits, typename PolicyHook>
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700550inline void
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800551trie<FullKey, PayloadTraits, PolicyHook>::PrintStat(std::ostream& os) const
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700552{
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800553 os << "# " << key_ << ((payload_ != PayloadTraits::empty_payload) ? "*" : "") << ": "
554 << children_.size() << " children" << std::endl;
555 for (size_t bucket = 0, maxbucket = children_.bucket_count(); bucket < maxbucket; bucket++) {
556 os << " " << children_.bucket_size(bucket);
557 }
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700558 os << "\n";
559
Alexander Afanasyev30f60e32012-07-10 14:21:16 -0700560 typedef trie<FullKey, PayloadTraits, PolicyHook> trie;
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800561 for (typename trie::unordered_set::const_iterator subnode = children_.begin();
562 subnode != children_.end(); subnode++)
Alexander Afanasyev051d3782012-07-03 10:10:15 -0700563 // BOOST_FOREACH (const trie &subnode, children_)
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800564 {
565 subnode->PrintStat(os);
566 }
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700567}
568
Alexander Afanasyev30f60e32012-07-10 14:21:16 -0700569template<typename FullKey, typename PayloadTraits, typename PolicyHook>
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700570inline bool
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800571operator==(const trie<FullKey, PayloadTraits, PolicyHook>& a,
572 const trie<FullKey, PayloadTraits, PolicyHook>& b)
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700573{
574 return a.key_ == b.key_;
575}
576
Alexander Afanasyev30f60e32012-07-10 14:21:16 -0700577template<typename FullKey, typename PayloadTraits, typename PolicyHook>
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700578inline std::size_t
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800579hash_value(const trie<FullKey, PayloadTraits, PolicyHook>& trie_node)
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700580{
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800581 return boost::hash_value(trie_node.key_);
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700582}
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700583
Alexander Afanasyev1cb4aad2012-08-09 14:58:16 -0700584template<class Trie, class NonConstTrie> // hack for boost < 1.47
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800585class trie_iterator {
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700586public:
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800587 trie_iterator()
588 : trie_(0)
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700589 {
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800590 }
591 trie_iterator(typename Trie::iterator item)
592 : trie_(item)
593 {
594 }
595 trie_iterator(Trie& item)
596 : trie_(&item)
597 {
598 }
599
600 Trie& operator*()
601 {
602 return *trie_;
603 }
604 const Trie& operator*() const
605 {
606 return *trie_;
607 }
608 Trie* operator->()
609 {
610 return trie_;
611 }
612 const Trie* operator->() const
613 {
614 return trie_;
615 }
616 bool
617 operator==(trie_iterator<const Trie, NonConstTrie>& other) const
618 {
619 return (trie_ == other.trie_);
620 }
621 bool
622 operator==(trie_iterator<Trie, NonConstTrie>& other)
623 {
624 return (trie_ == other.trie_);
625 }
626 bool
627 operator!=(trie_iterator<const Trie, NonConstTrie>& other) const
628 {
629 return !(*this == other);
630 }
631 bool
632 operator!=(trie_iterator<Trie, NonConstTrie>& other)
633 {
634 return !(*this == other);
635 }
636
637 trie_iterator<Trie, NonConstTrie>&
638 operator++(int)
639 {
640 if (trie_->children_.size() > 0)
641 trie_ = &(*trie_->children_.begin());
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700642 else
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800643 trie_ = goUp();
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700644 return *this;
645 }
646
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800647 trie_iterator<Trie, NonConstTrie>&
648 operator++()
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700649 {
650 (*this)++;
651 return *this;
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800652 }
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700653
654private:
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800655 typedef typename boost::mpl::if_<boost::is_same<Trie, NonConstTrie>,
656 typename Trie::unordered_set::iterator,
657 typename Trie::unordered_set::const_iterator>::type set_iterator;
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800658
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800659 Trie*
660 goUp()
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700661 {
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800662 if (trie_->parent_ != 0) {
663 // typename Trie::unordered_set::iterator item =
664 set_iterator item = const_cast<NonConstTrie*>(trie_)
665 ->parent_->children_.iterator_to(const_cast<NonConstTrie&>(*trie_));
666 item++;
667 if (item != trie_->parent_->children_.end()) {
668 return &(*item);
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700669 }
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800670 else {
671 trie_ = trie_->parent_;
672 return goUp();
673 }
674 }
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700675 else
676 return 0;
677 }
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800678
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700679private:
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800680 Trie* trie_;
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700681};
682
Alexander Afanasyev0845c092012-07-13 17:45:33 -0700683template<class Trie>
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800684class trie_point_iterator {
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800685private:
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800686 typedef typename boost::mpl::if_<boost::is_same<Trie, const Trie>,
687 typename Trie::unordered_set::const_iterator,
688 typename Trie::unordered_set::iterator>::type set_iterator;
Alexander Afanasyev0845c092012-07-13 17:45:33 -0700689
690public:
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800691 trie_point_iterator()
692 : trie_(0)
Alexander Afanasyev0845c092012-07-13 17:45:33 -0700693 {
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800694 }
695 trie_point_iterator(typename Trie::iterator item)
696 : trie_(item)
697 {
698 }
699 trie_point_iterator(Trie& item)
700 {
701 if (item.children_.size() != 0)
702 trie_ = &*item.children_.begin();
Alexander Afanasyev0845c092012-07-13 17:45:33 -0700703 else
704 trie_ = 0;
705 }
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800706
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800707 Trie& operator*()
Alexander Afanasyev0845c092012-07-13 17:45:33 -0700708 {
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800709 return *trie_;
710 }
711 const Trie& operator*() const
712 {
713 return *trie_;
714 }
715 Trie* operator->()
716 {
717 return trie_;
718 }
719 const Trie* operator->() const
720 {
721 return trie_;
722 }
723 bool
724 operator==(trie_point_iterator<const Trie>& other) const
725 {
726 return (trie_ == other.trie_);
727 }
728 bool
729 operator==(trie_point_iterator<Trie>& other)
730 {
731 return (trie_ == other.trie_);
732 }
733 bool
734 operator!=(trie_point_iterator<const Trie>& other) const
735 {
736 return !(*this == other);
737 }
738 bool
739 operator!=(trie_point_iterator<Trie>& other)
740 {
741 return !(*this == other);
742 }
743
744 trie_point_iterator<Trie>&
745 operator++(int)
746 {
747 if (trie_->parent_ != 0) {
748 set_iterator item = trie_->parent_->children_.iterator_to(*trie_);
749 item++;
750 if (item == trie_->parent_->children_.end())
Alexander Afanasyev0845c092012-07-13 17:45:33 -0700751 trie_ = 0;
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800752 else
753 trie_ = &*item;
754 }
755 else {
756 trie_ = 0;
757 }
Alexander Afanasyev0845c092012-07-13 17:45:33 -0700758 return *this;
759 }
760
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800761 trie_point_iterator<Trie>&
762 operator++()
Alexander Afanasyev0845c092012-07-13 17:45:33 -0700763 {
764 (*this)++;
765 return *this;
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800766 }
Alexander Afanasyev0845c092012-07-13 17:45:33 -0700767
768private:
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800769 Trie* trie_;
Alexander Afanasyev0845c092012-07-13 17:45:33 -0700770};
771
Alexander Afanasyev30cb1172012-07-06 10:47:39 -0700772} // ndnSIM
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700773} // ndn
Alexander Afanasyeve77db792012-08-09 11:10:58 -0700774} // ns3
Alexander Afanasyev30cb1172012-07-06 10:47:39 -0700775
Spyridon Mastorakis460f57c2014-12-17 00:44:14 -0800776/// @endcond
777
Alexander Afanasyev9a989702012-06-29 17:44:00 -0700778#endif // TRIE_H_