blob: dd10e6da77347a1a2737b956c729f97c1ec38e95 [file] [log] [blame]
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -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
Alexander Afanasyev9a989702012-06-29 17:44:00 -070021#ifndef TRIE_H_
22#define TRIE_H_
23
Spyridon Mastorakis53e922f2014-10-17 17:29:26 -070024#include "ns3/ndnSIM/model/ndn-common.hpp"
25
Alexander Afanasyev9a989702012-06-29 17:44:00 -070026#include "ns3/ptr.h"
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -070027
28#include <boost/intrusive/unordered_set.hpp>
Alexander Afanasyev89fb5352012-06-12 22:43:16 -070029#include <boost/intrusive/list.hpp>
Alexander Afanasyev9a989702012-06-29 17:44:00 -070030#include <boost/intrusive/set.hpp>
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -070031#include <boost/functional/hash.hpp>
Alexander Afanasyev89fb5352012-06-12 22:43:16 -070032#include <boost/interprocess/smart_ptr/unique_ptr.hpp>
Alexander Afanasyev07179012014-12-21 00:23:04 -080033#include <tuple>
Alexander Afanasyev78057c32012-07-06 15:18:46 -070034#include <boost/foreach.hpp>
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -070035#include <boost/mpl/if.hpp>
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -070036
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070037namespace ns3 {
38namespace ndn {
39namespace ndnSIM {
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -070040
41/////////////////////////////////////////////////////
42// Allow customization for payload
43//
Alexander Afanasyev8566f452012-12-10 15:21:51 -080044template<typename Payload, typename BasePayload = Payload>
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080045struct pointer_payload_traits {
46 typedef Payload payload_type; // general type of the payload
47 typedef Payload* storage_type; // how the payload is actually stored
48 typedef Payload* insert_type; // what parameter is inserted
Alexander Afanasyev0845c092012-07-13 17:45:33 -070049
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080050 typedef Payload* return_type; // what is returned on access
51 typedef const Payload* const_return_type; // what is returned on const access
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -070052
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080053 typedef BasePayload*
54 base_type; // base type of the entry (when implementation details need to be hidden)
55 typedef const BasePayload*
56 const_base_type; // const base type of the entry (when implementation details need to be hidden)
Alexander Afanasyeveec66292013-02-06 16:23:21 -080057
Alexander Afanasyev78057c32012-07-06 15:18:46 -070058 static Payload* empty_payload;
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -070059};
60
Alexander Afanasyev8566f452012-12-10 15:21:51 -080061template<typename Payload, typename BasePayload>
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080062Payload* pointer_payload_traits<Payload, BasePayload>::empty_payload = 0;
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -070063
Alexander Afanasyev8566f452012-12-10 15:21:51 -080064template<typename Payload, typename BasePayload = Payload>
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080065struct smart_pointer_payload_traits {
66 typedef Payload payload_type;
67 typedef ns3::Ptr<Payload> storage_type;
68 typedef ns3::Ptr<Payload> insert_type;
Alexander Afanasyeveec66292013-02-06 16:23:21 -080069
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080070 typedef ns3::Ptr<Payload> return_type;
Alexander Afanasyev0845c092012-07-13 17:45:33 -070071 typedef ns3::Ptr<const Payload> const_return_type;
Alexander Afanasyev8566f452012-12-10 15:21:51 -080072
73 typedef ns3::Ptr<BasePayload> base_type;
74 typedef ns3::Ptr<const BasePayload> const_base_type;
Alexander Afanasyeveec66292013-02-06 16:23:21 -080075
Alexander Afanasyev78057c32012-07-06 15:18:46 -070076 static ns3::Ptr<Payload> empty_payload;
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -070077};
78
Alexander Afanasyev8566f452012-12-10 15:21:51 -080079template<typename Payload, typename BasePayload>
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080080ns3::Ptr<Payload> smart_pointer_payload_traits<Payload, BasePayload>::empty_payload = 0;
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -070081
Alexander Afanasyev8566f452012-12-10 15:21:51 -080082template<typename Payload, typename BasePayload = Payload>
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080083struct non_pointer_traits {
84 typedef Payload payload_type;
85 typedef Payload storage_type;
86 typedef const Payload& insert_type; // nothing to insert
Alexander Afanasyev0845c092012-07-13 17:45:33 -070087
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080088 typedef Payload& return_type;
89 typedef const Payload& const_return_type;
Alexander Afanasyeveec66292013-02-06 16:23:21 -080090
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080091 typedef BasePayload& base_type;
Alexander Afanasyev62304f22012-12-10 18:06:21 -080092 typedef const BasePayload& const_base_type;
Alexander Afanasyeveec66292013-02-06 16:23:21 -080093
Alexander Afanasyev0845c092012-07-13 17:45:33 -070094 static Payload empty_payload;
95};
96
Alexander Afanasyev8566f452012-12-10 15:21:51 -080097template<typename Payload, typename BasePayload>
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080098Payload non_pointer_traits<Payload, BasePayload>::empty_payload = Payload();
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -070099
100////////////////////////////////////////////////////
101// forward declarations
102//
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800103template<typename FullKey, typename PayloadTraits, typename PolicyHook>
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800104class trie;
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700105
Alexander Afanasyev30f60e32012-07-10 14:21:16 -0700106template<typename FullKey, typename PayloadTraits, typename PolicyHook>
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700107inline std::ostream&
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800108operator<<(std::ostream& os, const trie<FullKey, PayloadTraits, PolicyHook>& trie_node);
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700109
Alexander Afanasyev30f60e32012-07-10 14:21:16 -0700110template<typename FullKey, typename PayloadTraits, typename PolicyHook>
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700111bool
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800112operator==(const trie<FullKey, PayloadTraits, PolicyHook>& a,
113 const trie<FullKey, PayloadTraits, PolicyHook>& b);
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700114
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800115template<typename FullKey, typename PayloadTraits, typename PolicyHook>
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700116std::size_t
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800117hash_value(const trie<FullKey, PayloadTraits, PolicyHook>& trie_node);
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700118
119///////////////////////////////////////////////////
120// actual definition
121//
Alexander Afanasyev1cb4aad2012-08-09 14:58:16 -0700122template<class T, class NonConstT>
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700123class trie_iterator;
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700124
Alexander Afanasyev0845c092012-07-13 17:45:33 -0700125template<class T>
126class trie_point_iterator;
127
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800128template<typename FullKey, typename PayloadTraits, typename PolicyHook>
129class trie {
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700130public:
Spyridon Mastorakis1f1cd5e2014-12-04 11:12:40 -0800131 typedef typename FullKey::value_type Key;
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700132
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800133 typedef trie* iterator;
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700134 typedef const trie* const_iterator;
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700135
Alexander Afanasyev1cb4aad2012-08-09 14:58:16 -0700136 typedef trie_iterator<trie, trie> recursive_iterator;
137 typedef trie_iterator<const trie, trie> const_recursive_iterator;
Alexander Afanasyev30f60e32012-07-10 14:21:16 -0700138
Alexander Afanasyev0845c092012-07-13 17:45:33 -0700139 typedef trie_point_iterator<trie> point_iterator;
140 typedef trie_point_iterator<const trie> const_point_iterator;
141
Alexander Afanasyev30f60e32012-07-10 14:21:16 -0700142 typedef PayloadTraits payload_traits;
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800143
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800144 inline trie(const Key& key, size_t bucketSize = 1, size_t bucketIncrement = 1)
145 : key_(key)
146 , initialBucketSize_(bucketSize)
147 , bucketIncrement_(bucketIncrement)
148 , bucketSize_(initialBucketSize_)
149 , buckets_(new bucket_type[bucketSize_]) // cannot use normal pointer, because lifetime of
150 // buckets should be larger than lifetime of the
151 // container
152 , children_(bucket_traits(buckets_.get(), bucketSize_))
153 , payload_(PayloadTraits::empty_payload)
154 , parent_(0)
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700155 {
156 }
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700157
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800158 inline ~trie()
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700159 {
160 payload_ = PayloadTraits::empty_payload; // necessary for smart pointers...
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800161 children_.clear_and_dispose(trie_delete_disposer());
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700162 }
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700163
164 void
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800165 clear()
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700166 {
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800167 children_.clear_and_dispose(trie_delete_disposer());
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700168 }
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700169
170 template<class Predicate>
171 void
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800172 clear_if(Predicate cond)
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700173 {
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800174 recursive_iterator trieNode(this);
175 recursive_iterator end(0);
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700176
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800177 while (trieNode != end) {
178 if (cond(*trieNode)) {
179 trieNode = recursive_iterator(trieNode->erase());
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700180 }
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800181 trieNode++;
182 }
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700183 }
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800184
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700185 // actual entry
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800186 friend bool operator==<>(const trie<FullKey, PayloadTraits, PolicyHook>& a,
187 const trie<FullKey, PayloadTraits, PolicyHook>& b);
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700188
189 friend std::size_t
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800190 hash_value<>(const trie<FullKey, PayloadTraits, PolicyHook>& trie_node);
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700191
192 inline std::pair<iterator, bool>
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800193 insert(const FullKey& key, typename PayloadTraits::insert_type payload)
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700194 {
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800195 trie* trieNode = this;
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800196
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800197 BOOST_FOREACH (const Key& subkey, key) {
198 typename unordered_set::iterator item = trieNode->children_.find(subkey);
199 if (item == trieNode->children_.end()) {
200 trie* newNode = new trie(subkey, initialBucketSize_, bucketIncrement_);
201 // std::cout << "new " << newNode << "\n";
202 newNode->parent_ = trieNode;
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700203
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800204 if (trieNode->children_.size() >= trieNode->bucketSize_) {
205 trieNode->bucketSize_ += trieNode->bucketIncrement_;
206 trieNode->bucketIncrement_ *= 2; // increase bucketIncrement exponentially
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800207
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800208 buckets_array newBuckets(new bucket_type[trieNode->bucketSize_]);
209 trieNode->children_.rehash(bucket_traits(newBuckets.get(), trieNode->bucketSize_));
210 trieNode->buckets_.swap(newBuckets);
211 }
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800212
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800213 std::pair<typename unordered_set::iterator, bool> ret =
214 trieNode->children_.insert(*newNode);
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800215
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800216 trieNode = &(*ret.first);
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700217 }
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800218 else
219 trieNode = &(*item);
220 }
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700221
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800222 if (trieNode->payload_ == PayloadTraits::empty_payload) {
223 trieNode->payload_ = payload;
224 return std::make_pair(trieNode, true);
225 }
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700226 else
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800227 return std::make_pair(trieNode, false);
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700228 }
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700229
230 /**
231 * @brief Removes payload (if it exists) and if there are no children, prunes parents trie
232 */
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700233 inline iterator
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800234 erase()
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700235 {
236 payload_ = PayloadTraits::empty_payload;
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800237 return prune();
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700238 }
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700239
240 /**
241 * @brief Do exactly as erase, but without erasing the payload
242 */
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700243 inline iterator
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800244 prune()
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700245 {
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800246 if (payload_ == PayloadTraits::empty_payload && children_.size() == 0) {
247 if (parent_ == 0)
248 return this;
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700249
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800250 trie* parent = parent_;
251 parent->children_
252 .erase_and_dispose(*this,
253 trie_delete_disposer()); // delete this; basically, committing a suicide
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700254
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800255 return parent->prune();
256 }
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700257 return this;
258 }
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700259
Alexander Afanasyev70426a02012-08-15 15:39:18 -0700260 /**
261 * @brief Perform prune of the node, but without attempting to parent of the node
262 */
263 inline void
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800264 prune_node()
Alexander Afanasyev70426a02012-08-15 15:39:18 -0700265 {
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800266 if (payload_ == PayloadTraits::empty_payload && children_.size() == 0) {
267 if (parent_ == 0)
268 return;
Alexander Afanasyev70426a02012-08-15 15:39:18 -0700269
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800270 trie* parent = parent_;
271 parent->children_
272 .erase_and_dispose(*this,
273 trie_delete_disposer()); // delete this; basically, committing a suicide
274 }
Alexander Afanasyev70426a02012-08-15 15:39:18 -0700275 }
276
Alexander Afanasyev07179012014-12-21 00:23:04 -0800277 // inline std::tuple<const iterator, bool, const iterator>
Alexander Afanasyev30f60e32012-07-10 14:21:16 -0700278 // find (const FullKey &key) const
279 // {
280 // return const_cast<trie*> (this)->find (key);
281 // }
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700282
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700283 /**
284 * @brief Perform the longest prefix match
285 * @param key the key for which to perform the longest prefix match
286 *
287 * @return ->second is true if prefix in ->first is longer than key
288 */
Alexander Afanasyev07179012014-12-21 00:23:04 -0800289 inline std::tuple<iterator, bool, iterator>
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800290 find(const FullKey& key)
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700291 {
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800292 trie* trieNode = this;
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700293 iterator foundNode = (payload_ != PayloadTraits::empty_payload) ? this : 0;
294 bool reachLast = true;
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800295
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800296 BOOST_FOREACH (const Key& subkey, key) {
297 typename unordered_set::iterator item = trieNode->children_.find(subkey);
298 if (item == trieNode->children_.end()) {
299 reachLast = false;
300 break;
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700301 }
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800302 else {
303 trieNode = &(*item);
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700304
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800305 if (trieNode->payload_ != PayloadTraits::empty_payload)
306 foundNode = trieNode;
307 }
308 }
309
Alexander Afanasyev07179012014-12-21 00:23:04 -0800310 return std::make_tuple(foundNode, reachLast, trieNode);
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800311 }
312
313 /**
314 * @brief Perform the longest prefix match satisfying preficate
315 * @param key the key for which to perform the longest prefix match
316 *
317 * @return ->second is true if prefix in ->first is longer than key
318 */
319 template<class Predicate>
Alexander Afanasyev07179012014-12-21 00:23:04 -0800320 inline std::tuple<iterator, bool, iterator>
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800321 find_if(const FullKey& key, Predicate pred)
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800322 {
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800323 trie* trieNode = this;
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800324 iterator foundNode = (payload_ != PayloadTraits::empty_payload) ? this : 0;
325 bool reachLast = true;
326
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800327 BOOST_FOREACH (const Key& subkey, key) {
328 typename unordered_set::iterator item = trieNode->children_.find(subkey);
329 if (item == trieNode->children_.end()) {
330 reachLast = false;
331 break;
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800332 }
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800333 else {
334 trieNode = &(*item);
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800335
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800336 if (trieNode->payload_ != PayloadTraits::empty_payload && pred(trieNode->payload_)) {
337 foundNode = trieNode;
338 }
339 }
340 }
341
Alexander Afanasyev07179012014-12-21 00:23:04 -0800342 return std::make_tuple(foundNode, reachLast, trieNode);
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700343 }
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700344
345 /**
346 * @brief Find next payload of the sub-trie
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800347 * @returns end() or a valid iterator pointing to the trie leaf (order is not defined, enumeration
348 * )
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700349 */
350 inline iterator
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800351 find()
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700352 {
353 if (payload_ != PayloadTraits::empty_payload)
354 return this;
355
Alexander Afanasyev30f60e32012-07-10 14:21:16 -0700356 typedef trie<FullKey, PayloadTraits, PolicyHook> trie;
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800357 for (typename trie::unordered_set::iterator subnode = children_.begin();
358 subnode != children_.end(); subnode++)
359 // BOOST_FOREACH (trie &subnode, children_)
360 {
361 iterator value = subnode->find();
362 if (value != 0)
363 return value;
364 }
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800365
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700366 return 0;
367 }
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700368
369 /**
370 * @brief Find next payload of the sub-trie satisfying the predicate
371 * @param pred predicate
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800372 * @returns end() or a valid iterator pointing to the trie leaf (order is not defined, enumeration
373 * )
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700374 */
375 template<class Predicate>
Alexander Afanasyev30f60e32012-07-10 14:21:16 -0700376 inline const iterator
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800377 find_if(Predicate pred)
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700378 {
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800379 if (payload_ != PayloadTraits::empty_payload && pred(payload_))
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700380 return this;
381
Alexander Afanasyev30f60e32012-07-10 14:21:16 -0700382 typedef trie<FullKey, PayloadTraits, PolicyHook> trie;
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800383 for (typename trie::unordered_set::iterator subnode = children_.begin();
384 subnode != children_.end(); subnode++)
385 // BOOST_FOREACH (const trie &subnode, children_)
386 {
387 iterator value = subnode->find_if(pred);
388 if (value != 0)
389 return value;
390 }
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800391
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700392 return 0;
393 }
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700394
Alexander Afanasyeveec89ba2013-07-19 16:34:30 -0700395 /**
396 * @brief Find next payload of the sub-trie satisfying the predicate
397 * @param pred predicate
398 *
399 * This version check predicate only for the next level children
400 *
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800401 * @returns end() or a valid iterator pointing to the trie leaf (order is not defined, enumeration
402 *)
Alexander Afanasyeveec89ba2013-07-19 16:34:30 -0700403 */
404 template<class Predicate>
405 inline const iterator
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800406 find_if_next_level(Predicate pred)
Alexander Afanasyeveec89ba2013-07-19 16:34:30 -0700407 {
408 typedef trie<FullKey, PayloadTraits, PolicyHook> trie;
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800409 for (typename trie::unordered_set::iterator subnode = children_.begin();
410 subnode != children_.end(); subnode++) {
411 if (pred(subnode->key())) {
412 return subnode->find();
Alexander Afanasyeveec89ba2013-07-19 16:34:30 -0700413 }
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800414 }
Alexander Afanasyeveec89ba2013-07-19 16:34:30 -0700415
416 return 0;
417 }
418
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800419 iterator
420 end()
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700421 {
422 return 0;
423 }
424
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800425 const_iterator
426 end() const
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700427 {
428 return 0;
429 }
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700430
Alexander Afanasyev0845c092012-07-13 17:45:33 -0700431 typename PayloadTraits::const_return_type
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800432 payload() const
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700433 {
434 return payload_;
435 }
436
Alexander Afanasyev0845c092012-07-13 17:45:33 -0700437 typename PayloadTraits::return_type
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800438 payload()
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700439 {
440 return payload_;
441 }
442
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700443 void
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800444 set_payload(typename PayloadTraits::insert_type payload)
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700445 {
446 payload_ = payload;
447 }
Alexander Afanasyev0560eec2012-07-16 15:44:31 -0700448
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800449 Key
450 key() const
Alexander Afanasyev0560eec2012-07-16 15:44:31 -0700451 {
452 return key_;
453 }
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800454
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700455 inline void
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800456 PrintStat(std::ostream& os) const;
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800457
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700458private:
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800459 // The disposer object function
460 struct trie_delete_disposer {
461 void
462 operator()(trie* delete_this)
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700463 {
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700464 delete delete_this;
465 }
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700466 };
467
468 template<class D>
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800469 struct array_disposer {
470 void
471 operator()(D* array)
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700472 {
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800473 delete[] array;
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700474 }
475 };
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700476
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800477 friend std::ostream& operator<<<>(std::ostream& os, const trie& trie_node);
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700478
479public:
480 PolicyHook policy_hook_;
481
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700482private:
Alexander Afanasyev30cb1172012-07-06 10:47:39 -0700483 boost::intrusive::unordered_set_member_hook<> unordered_set_member_hook_;
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700484
485 // necessary typedefs
486 typedef trie self_type;
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800487 typedef boost::intrusive::member_hook<trie, boost::intrusive::unordered_set_member_hook<>,
488 &trie::unordered_set_member_hook_> member_hook;
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700489
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800490 typedef boost::intrusive::unordered_set<trie, member_hook> unordered_set;
491 typedef typename unordered_set::bucket_type bucket_type;
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700492 typedef typename unordered_set::bucket_traits bucket_traits;
493
Alexander Afanasyev1cb4aad2012-08-09 14:58:16 -0700494 template<class T, class NonConstT>
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700495 friend class trie_iterator;
Alexander Afanasyev0845c092012-07-13 17:45:33 -0700496
497 template<class T>
498 friend class trie_point_iterator;
499
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700500 ////////////////////////////////////////////////
501 // Actual data
502 ////////////////////////////////////////////////
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800503
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700504 Key key_; ///< name component
505
506 size_t initialBucketSize_;
507 size_t bucketIncrement_;
508
509 size_t bucketSize_;
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800510 typedef boost::interprocess::unique_ptr<bucket_type, array_disposer<bucket_type>> buckets_array;
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700511 buckets_array buckets_;
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700512 unordered_set children_;
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800513
Alexander Afanasyev0845c092012-07-13 17:45:33 -0700514 typename PayloadTraits::storage_type payload_;
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800515 trie* parent_; // to make cleaning effective
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700516};
517
Alexander Afanasyev30f60e32012-07-10 14:21:16 -0700518template<typename FullKey, typename PayloadTraits, typename PolicyHook>
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700519inline std::ostream&
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800520operator<<(std::ostream& os, const trie<FullKey, PayloadTraits, PolicyHook>& trie_node)
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700521{
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800522 os << "# " << trie_node.key_ << ((trie_node.payload_ != PayloadTraits::empty_payload) ? "*" : "")
523 << std::endl;
Alexander Afanasyev30f60e32012-07-10 14:21:16 -0700524 typedef trie<FullKey, PayloadTraits, PolicyHook> trie;
Alexander Afanasyev051d3782012-07-03 10:10:15 -0700525
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800526 for (typename trie::unordered_set::const_iterator subnode = trie_node.children_.begin();
527 subnode != trie_node.children_.end(); subnode++)
Alexander Afanasyev051d3782012-07-03 10:10:15 -0700528 // BOOST_FOREACH (const trie &subnode, trie_node.children_)
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800529 {
530 os << "\"" << &trie_node << "\""
531 << " [label=\"" << trie_node.key_
532 << ((trie_node.payload_ != PayloadTraits::empty_payload) ? "*" : "") << "\"]\n";
533 os << "\"" << &(*subnode) << "\""
534 << " [label=\"" << subnode->key_
535 << ((subnode->payload_ != PayloadTraits::empty_payload) ? "*" : "") << "\"]"
536 "\n";
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800537
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800538 os << "\"" << &trie_node << "\""
539 << " -> "
540 << "\"" << &(*subnode) << "\""
541 << "\n";
542 os << *subnode;
543 }
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700544
545 return os;
546}
547
Alexander Afanasyev30f60e32012-07-10 14:21:16 -0700548template<typename FullKey, typename PayloadTraits, typename PolicyHook>
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700549inline void
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800550trie<FullKey, PayloadTraits, PolicyHook>::PrintStat(std::ostream& os) const
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700551{
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800552 os << "# " << key_ << ((payload_ != PayloadTraits::empty_payload) ? "*" : "") << ": "
553 << children_.size() << " children" << std::endl;
554 for (size_t bucket = 0, maxbucket = children_.bucket_count(); bucket < maxbucket; bucket++) {
555 os << " " << children_.bucket_size(bucket);
556 }
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700557 os << "\n";
558
Alexander Afanasyev30f60e32012-07-10 14:21:16 -0700559 typedef trie<FullKey, PayloadTraits, PolicyHook> trie;
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800560 for (typename trie::unordered_set::const_iterator subnode = children_.begin();
561 subnode != children_.end(); subnode++)
Alexander Afanasyev051d3782012-07-03 10:10:15 -0700562 // BOOST_FOREACH (const trie &subnode, children_)
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800563 {
564 subnode->PrintStat(os);
565 }
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700566}
567
Alexander Afanasyev30f60e32012-07-10 14:21:16 -0700568template<typename FullKey, typename PayloadTraits, typename PolicyHook>
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700569inline bool
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800570operator==(const trie<FullKey, PayloadTraits, PolicyHook>& a,
571 const trie<FullKey, PayloadTraits, PolicyHook>& b)
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700572{
573 return a.key_ == b.key_;
574}
575
Alexander Afanasyev30f60e32012-07-10 14:21:16 -0700576template<typename FullKey, typename PayloadTraits, typename PolicyHook>
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700577inline std::size_t
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800578hash_value(const trie<FullKey, PayloadTraits, PolicyHook>& trie_node)
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700579{
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800580 return boost::hash_value(trie_node.key_);
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700581}
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700582
Alexander Afanasyev1cb4aad2012-08-09 14:58:16 -0700583template<class Trie, class NonConstTrie> // hack for boost < 1.47
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800584class trie_iterator {
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700585public:
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800586 trie_iterator()
587 : trie_(0)
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700588 {
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800589 }
590 trie_iterator(typename Trie::iterator item)
591 : trie_(item)
592 {
593 }
594 trie_iterator(Trie& item)
595 : trie_(&item)
596 {
597 }
598
599 Trie& operator*()
600 {
601 return *trie_;
602 }
603 const Trie& operator*() const
604 {
605 return *trie_;
606 }
607 Trie* operator->()
608 {
609 return trie_;
610 }
611 const Trie* operator->() const
612 {
613 return trie_;
614 }
615 bool
616 operator==(trie_iterator<const Trie, NonConstTrie>& other) const
617 {
618 return (trie_ == other.trie_);
619 }
620 bool
621 operator==(trie_iterator<Trie, NonConstTrie>& other)
622 {
623 return (trie_ == other.trie_);
624 }
625 bool
626 operator!=(trie_iterator<const Trie, NonConstTrie>& other) const
627 {
628 return !(*this == other);
629 }
630 bool
631 operator!=(trie_iterator<Trie, NonConstTrie>& other)
632 {
633 return !(*this == other);
634 }
635
636 trie_iterator<Trie, NonConstTrie>&
637 operator++(int)
638 {
639 if (trie_->children_.size() > 0)
640 trie_ = &(*trie_->children_.begin());
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700641 else
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800642 trie_ = goUp();
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700643 return *this;
644 }
645
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800646 trie_iterator<Trie, NonConstTrie>&
647 operator++()
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700648 {
649 (*this)++;
650 return *this;
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800651 }
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700652
653private:
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800654 typedef typename boost::mpl::if_<boost::is_same<Trie, NonConstTrie>,
655 typename Trie::unordered_set::iterator,
656 typename Trie::unordered_set::const_iterator>::type set_iterator;
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800657
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800658 Trie*
659 goUp()
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700660 {
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800661 if (trie_->parent_ != 0) {
662 // typename Trie::unordered_set::iterator item =
663 set_iterator item = const_cast<NonConstTrie*>(trie_)
664 ->parent_->children_.iterator_to(const_cast<NonConstTrie&>(*trie_));
665 item++;
666 if (item != trie_->parent_->children_.end()) {
667 return &(*item);
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700668 }
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800669 else {
670 trie_ = trie_->parent_;
671 return goUp();
672 }
673 }
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700674 else
675 return 0;
676 }
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800677
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700678private:
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800679 Trie* trie_;
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700680};
681
Alexander Afanasyev0845c092012-07-13 17:45:33 -0700682template<class Trie>
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800683class trie_point_iterator {
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800684private:
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800685 typedef typename boost::mpl::if_<boost::is_same<Trie, const Trie>,
686 typename Trie::unordered_set::const_iterator,
687 typename Trie::unordered_set::iterator>::type set_iterator;
Alexander Afanasyev0845c092012-07-13 17:45:33 -0700688
689public:
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800690 trie_point_iterator()
691 : trie_(0)
Alexander Afanasyev0845c092012-07-13 17:45:33 -0700692 {
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800693 }
694 trie_point_iterator(typename Trie::iterator item)
695 : trie_(item)
696 {
697 }
698 trie_point_iterator(Trie& item)
699 {
700 if (item.children_.size() != 0)
701 trie_ = &*item.children_.begin();
Alexander Afanasyev0845c092012-07-13 17:45:33 -0700702 else
703 trie_ = 0;
704 }
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800705
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800706 Trie& operator*()
Alexander Afanasyev0845c092012-07-13 17:45:33 -0700707 {
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800708 return *trie_;
709 }
710 const Trie& operator*() const
711 {
712 return *trie_;
713 }
714 Trie* operator->()
715 {
716 return trie_;
717 }
718 const Trie* operator->() const
719 {
720 return trie_;
721 }
722 bool
723 operator==(trie_point_iterator<const Trie>& other) const
724 {
725 return (trie_ == other.trie_);
726 }
727 bool
728 operator==(trie_point_iterator<Trie>& other)
729 {
730 return (trie_ == other.trie_);
731 }
732 bool
733 operator!=(trie_point_iterator<const Trie>& other) const
734 {
735 return !(*this == other);
736 }
737 bool
738 operator!=(trie_point_iterator<Trie>& other)
739 {
740 return !(*this == other);
741 }
742
743 trie_point_iterator<Trie>&
744 operator++(int)
745 {
746 if (trie_->parent_ != 0) {
747 set_iterator item = trie_->parent_->children_.iterator_to(*trie_);
748 item++;
749 if (item == trie_->parent_->children_.end())
Alexander Afanasyev0845c092012-07-13 17:45:33 -0700750 trie_ = 0;
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800751 else
752 trie_ = &*item;
753 }
754 else {
755 trie_ = 0;
756 }
Alexander Afanasyev0845c092012-07-13 17:45:33 -0700757 return *this;
758 }
759
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800760 trie_point_iterator<Trie>&
761 operator++()
Alexander Afanasyev0845c092012-07-13 17:45:33 -0700762 {
763 (*this)++;
764 return *this;
Alexander Afanasyeveec66292013-02-06 16:23:21 -0800765 }
Alexander Afanasyev0845c092012-07-13 17:45:33 -0700766
767private:
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800768 Trie* trie_;
Alexander Afanasyev0845c092012-07-13 17:45:33 -0700769};
770
Alexander Afanasyev30cb1172012-07-06 10:47:39 -0700771} // ndnSIM
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700772} // ndn
Alexander Afanasyeve77db792012-08-09 11:10:58 -0700773} // ns3
Alexander Afanasyev30cb1172012-07-06 10:47:39 -0700774
Alexander Afanasyev9a989702012-06-29 17:44:00 -0700775#endif // TRIE_H_