blob: f65e242a0bb9638802af8f50c522814af297490b [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
24#include "ns3/ptr.h"
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -070025
26#include <boost/intrusive/unordered_set.hpp>
Alexander Afanasyev89fb5352012-06-12 22:43:16 -070027#include <boost/intrusive/list.hpp>
Alexander Afanasyev9a989702012-06-29 17:44:00 -070028#include <boost/intrusive/set.hpp>
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -070029#include <boost/functional/hash.hpp>
Alexander Afanasyev89fb5352012-06-12 22:43:16 -070030#include <boost/interprocess/smart_ptr/unique_ptr.hpp>
31#include <boost/tuple/tuple.hpp>
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -070032
33namespace bi = boost::intrusive;
34
35/////////////////////////////////////////////////////
36// Allow customization for payload
37//
38template<typename Payload>
39struct pointer_payload_traits
40{
Alexander Afanasyev9e96e362012-07-02 23:04:39 -070041 typedef Payload payload_type;
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -070042 typedef Payload* pointer_type;
43 typedef const Payload* const_pointer_type;
44
45 static const Payload* empty_payload;
46};
47
48template<typename Payload>
49const Payload*
50pointer_payload_traits<Payload>::empty_payload = 0;
51
52template<typename Payload>
53struct smart_pointer_payload_traits
54{
Alexander Afanasyev9e96e362012-07-02 23:04:39 -070055 typedef Payload payload_type;
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -070056 typedef ns3::Ptr<Payload> pointer_type;
57 typedef ns3::Ptr<const Payload> const_pointer_type;
58
59 static const ns3::Ptr<const Payload> empty_payload;
60};
61
62template<typename Payload>
63const ns3::Ptr<const Payload>
64smart_pointer_payload_traits<Payload>::empty_payload = 0;
65
66
67////////////////////////////////////////////////////
68// forward declarations
69//
Alexander Afanasyev89fb5352012-06-12 22:43:16 -070070template<typename FullKey,
71 typename Payload,
Alexander Afanasyev9a989702012-06-29 17:44:00 -070072 typename PayloadTraits,
73 typename PolicyHook >
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -070074class trie;
75
Alexander Afanasyev89fb5352012-06-12 22:43:16 -070076template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook>
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -070077inline std::ostream&
Alexander Afanasyev89fb5352012-06-12 22:43:16 -070078operator << (std::ostream &os,
79 const trie<FullKey, Payload, PayloadTraits, PolicyHook> &trie_node);
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -070080
Alexander Afanasyev89fb5352012-06-12 22:43:16 -070081template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook>
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -070082bool
Alexander Afanasyev89fb5352012-06-12 22:43:16 -070083operator== (const trie<FullKey, Payload, PayloadTraits, PolicyHook> &a,
84 const trie<FullKey, Payload, PayloadTraits, PolicyHook> &b);
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -070085
Alexander Afanasyev89fb5352012-06-12 22:43:16 -070086template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook >
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -070087std::size_t
Alexander Afanasyev89fb5352012-06-12 22:43:16 -070088hash_value (const trie<FullKey, Payload, PayloadTraits, PolicyHook> &trie_node);
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -070089
90///////////////////////////////////////////////////
91// actual definition
92//
93
94
95template<typename FullKey,
Alexander Afanasyev89fb5352012-06-12 22:43:16 -070096 typename Payload, typename PayloadTraits,
97 typename PolicyHook >
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -070098class trie
99{
100public:
101 typedef typename FullKey::partial_type Key;
102
103 typedef trie* iterator;
104 typedef const trie* const_iterator;
105
106 inline
107 trie (const Key &key, size_t bucketSize = 10, size_t bucketIncrement = 10);
108
109 inline
110 ~trie ();
111
112 // actual entry
113 friend bool
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700114 operator== <> (const trie<FullKey, Payload, PayloadTraits, PolicyHook> &a,
115 const trie<FullKey, Payload, PayloadTraits, PolicyHook> &b);
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700116
117 friend std::size_t
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700118 hash_value <> (const trie<FullKey, Payload, PayloadTraits, PolicyHook> &trie_node);
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700119
120 inline std::pair<iterator, bool>
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700121 insert (const FullKey &key,
122 typename PayloadTraits::const_pointer_type payload);
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700123
124 /**
125 * @brief Removes payload (if it exists) and if there are no children, prunes parents trie
126 */
127 inline void
128 erase ();
129
130 /**
131 * @brief Do exactly as erase, but without erasing the payload
132 */
133 inline void
134 prune ();
135
136 /**
137 * @brief Perform the longest prefix match
138 * @param key the key for which to perform the longest prefix match
139 *
140 * @return ->second is true if prefix in ->first is longer than key
141 */
142 inline boost::tuple<iterator, bool, iterator>
143 find (const FullKey &key);
144
145 /**
146 * @brief Find next payload of the sub-trie
147 * @returns end() or a valid iterator pointing to the trie leaf (order is not defined, enumeration )
148 */
149 inline iterator
150 find ();
151
152 /**
153 * @brief Find next payload of the sub-trie satisfying the predicate
154 * @param pred predicate
155 * @returns end() or a valid iterator pointing to the trie leaf (order is not defined, enumeration )
156 */
157 template<class Predicate>
158 inline iterator
159 find_if (Predicate pred);
160
161 iterator end ()
162 {
163 return 0;
164 }
165
166 const_iterator end () const
167 {
168 return 0;
169 }
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700170
171 typename PayloadTraits::const_pointer_type
172 payload () const
173 {
174 return payload_;
175 }
176
177 void
178 set_payload (typename PayloadTraits::const_pointer_type payload)
179 {
180 payload_ = payload;
181 }
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700182
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700183 inline void
184 PrintStat (std::ostream &os) const;
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700185
186private:
187 //The disposer object function
188 struct trie_delete_disposer
189 {
190 void operator() (trie *delete_this)
191 {
192 // std::cout << "Deleting " << delete_this << "\n";
193 delete delete_this;
194 }
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700195 };
196
197 template<class D>
198 struct array_disposer
199 {
200 void operator() (D *array)
201 {
202 delete [] array;
203 }
204 };
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700205
206 friend
207 std::ostream&
208 operator<< < > (std::ostream &os, const trie &trie_node);
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700209
210public:
211 PolicyHook policy_hook_;
212
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700213private:
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700214 bi::unordered_set_member_hook<> unordered_set_member_hook_;
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700215
216 // necessary typedefs
217 typedef trie self_type;
218 typedef bi::member_hook< trie,
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700219 bi::unordered_set_member_hook< >, &trie::unordered_set_member_hook_ > member_hook;
220 typedef bi::unordered_set< trie, member_hook > unordered_set;
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700221 typedef typename unordered_set::bucket_type bucket_type;
222 typedef typename unordered_set::bucket_traits bucket_traits;
223
224 ////////////////////////////////////////////////
225 // Actual data
226 ////////////////////////////////////////////////
227
228 Key key_; ///< name component
229
230 size_t initialBucketSize_;
231 size_t bucketIncrement_;
232
233 size_t bucketSize_;
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700234 typedef boost::interprocess::unique_ptr< bucket_type, array_disposer<bucket_type> > buckets_array;
235 buckets_array buckets_;
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700236 unordered_set children_;
237
238 typename PayloadTraits::const_pointer_type payload_;
239 trie *parent_; // to make cleaning effective
240};
241
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700242template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook>
243trie<FullKey, Payload, PayloadTraits, PolicyHook>
244::trie (const trie::Key &key, size_t bucketSize, size_t bucketIncrement)
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700245 : key_ (key)
246 , initialBucketSize_ (bucketSize)
247 , bucketIncrement_ (bucketIncrement)
248 , bucketSize_ (initialBucketSize_)
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700249 , buckets_ (new bucket_type [bucketSize_]) //cannot use normal pointer, because lifetime of buckets should be larger than lifetime of the container
250 , children_ (bucket_traits (buckets_.get (), bucketSize_))
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700251 , payload_ (PayloadTraits::empty_payload)
252 , parent_ (0)
253{
254}
255
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700256template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook>
257trie<FullKey, Payload, PayloadTraits, PolicyHook>
258::~trie ()
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700259{
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700260 payload_ = PayloadTraits::empty_payload; // necessary for smart pointers...
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700261 children_.clear_and_dispose (trie_delete_disposer ());
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700262}
263
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700264template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook>
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700265inline
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700266std::pair<typename trie<FullKey, Payload, PayloadTraits, PolicyHook>::iterator, bool>
267trie<FullKey, Payload, PayloadTraits, PolicyHook>
268::insert (const FullKey &key, typename PayloadTraits::const_pointer_type payload)
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700269{
270 trie *trieNode = this;
271
272 BOOST_FOREACH (const Key &subkey, key)
273 {
274 typename unordered_set::iterator item = trieNode->children_.find (subkey);
275 if (item == trieNode->children_.end ())
276 {
277 trie *newNode = new trie (subkey, initialBucketSize_, bucketIncrement_);
278 // std::cout << "new " << newNode << "\n";
279 newNode->parent_ = trieNode;
280
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700281 if (trieNode->children_.size () >= trieNode->bucketSize_)
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700282 {
283 trieNode->bucketSize_ += trieNode->bucketIncrement_;
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700284 buckets_array newBuckets (new bucket_type [trieNode->bucketSize_]);
285 trieNode->children_.rehash (bucket_traits (newBuckets.get (), trieNode->bucketSize_));
286 trieNode->buckets_.swap (newBuckets);
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700287 }
288
289 std::pair< typename unordered_set::iterator, bool > ret =
290 trieNode->children_.insert (*newNode);
291
292 trieNode = &(*ret.first);
293 }
294 else
295 trieNode = &(*item);
296 }
297
298 if (trieNode->payload_ == 0)
299 {
300 trieNode->payload_ = payload;
301 return std::make_pair (trieNode, true);
302 }
303 else
304 return std::make_pair (trieNode, false);
305}
306
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700307template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook>
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700308inline
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700309boost::tuple<typename trie<FullKey, Payload, PayloadTraits, PolicyHook>::iterator,
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700310 bool,
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700311 typename trie<FullKey, Payload, PayloadTraits, PolicyHook>::iterator>
312trie<FullKey, Payload, PayloadTraits, PolicyHook>
313::find (const FullKey &key)
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700314{
315 trie *trieNode = this;
316 iterator foundNode = (payload_ != PayloadTraits::empty_payload) ? this : 0;
317 bool reachLast = true;
318
319 BOOST_FOREACH (const Key &subkey, key)
320 {
321 typename unordered_set::iterator item = trieNode->children_.find (subkey);
322 if (item == trieNode->children_.end ())
323 {
324 reachLast = false;
325 break;
326 }
327 else
328 {
329 trieNode = &(*item);
330
331 if (trieNode->payload_ != PayloadTraits::empty_payload)
332 foundNode = trieNode;
333 }
334 }
335
336 return boost::make_tuple (foundNode, reachLast, trieNode);
337}
338
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700339template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook>
340inline typename trie<FullKey, Payload, PayloadTraits, PolicyHook>::iterator
341trie<FullKey, Payload, PayloadTraits, PolicyHook>
342::find ()
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700343{
344 if (payload_ != PayloadTraits::empty_payload)
345 return this;
346
Alexander Afanasyev9a989702012-06-29 17:44:00 -0700347 typedef trie<FullKey, Payload, PayloadTraits, PolicyHook> trie;
Alexander Afanasyev051d3782012-07-03 10:10:15 -0700348 for (typename trie::unordered_set::iterator subnode = children_.begin ();
349 subnode != children_.end ();
350 subnode++ )
351 // BOOST_FOREACH (trie &subnode, children_)
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700352 {
Alexander Afanasyev051d3782012-07-03 10:10:15 -0700353 iterator value = subnode->find ();
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700354 if (value != 0)
355 return value;
356 }
357
358 return 0;
359}
360
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700361template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook>
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700362template<class Predicate>
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700363inline typename trie<FullKey, Payload, PayloadTraits, PolicyHook>::iterator
364trie<FullKey, Payload, PayloadTraits, PolicyHook>
365::find_if (Predicate pred)
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700366{
367 if (payload_ != PayloadTraits::empty_payload && pred (payload_))
368 return this;
369
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700370 typedef trie<FullKey, Payload, PayloadTraits, PolicyHook> trie;
Alexander Afanasyev051d3782012-07-03 10:10:15 -0700371 for (typename trie::unordered_set::iterator subnode = children_.begin ();
372 subnode != children_.end ();
373 subnode++ )
374 // BOOST_FOREACH (const trie &subnode, children_)
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700375 {
Alexander Afanasyev051d3782012-07-03 10:10:15 -0700376 iterator value = subnode->find ();
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700377 if (value != 0)
Alexander Afanasyev051d3782012-07-03 10:10:15 -0700378 return value;
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700379 }
380
381 return 0;
382}
383
384
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700385template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook>
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700386inline void
Alexander Afanasyevb0c43892012-06-13 00:52:58 -0700387trie<FullKey, Payload, PayloadTraits, PolicyHook>
388::erase ()
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700389{
390 payload_ = PayloadTraits::empty_payload;
391 prune ();
392}
393
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700394template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook>
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700395inline void
Alexander Afanasyevb0c43892012-06-13 00:52:58 -0700396trie<FullKey, Payload, PayloadTraits, PolicyHook>
397::prune ()
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700398{
399 if (payload_ == 0 && children_.size () == 0)
400 {
401 if (parent_ == 0) return;
402
403 trie *parent = parent_;
404 parent->children_.erase_and_dispose (*this, trie_delete_disposer ()); // delete this; basically, committing a suicide
405
406 parent->prune ();
407 }
408}
409
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700410template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook>
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700411inline std::ostream&
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700412operator << (std::ostream &os, const trie<FullKey, Payload, PayloadTraits, PolicyHook> &trie_node)
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700413{
414 os << "# " << trie_node.key_ << ((trie_node.payload_ != 0)?"*":"") << std::endl;
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700415 typedef trie<FullKey, Payload, PayloadTraits, PolicyHook> trie;
Alexander Afanasyev051d3782012-07-03 10:10:15 -0700416
417 for (typename trie::unordered_set::const_iterator subnode = trie_node.children_.begin ();
418 subnode != trie_node.children_.end ();
419 subnode++ )
420 // BOOST_FOREACH (const trie &subnode, trie_node.children_)
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700421 {
422 os << "\"" << &trie_node << "\"" << " [label=\"" << trie_node.key_ << ((trie_node.payload_ != 0)?"*":"") << "\"]\n";
Alexander Afanasyev051d3782012-07-03 10:10:15 -0700423 os << "\"" << &(*subnode) << "\"" << " [label=\"" << subnode->key_ << ((subnode->payload_ != 0)?"*":"") << "\"]""\n";
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700424
Alexander Afanasyev051d3782012-07-03 10:10:15 -0700425 os << "\"" << &trie_node << "\"" << " -> " << "\"" << &(*subnode) << "\"" << "\n";
426 os << *subnode;
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700427 }
428
429 return os;
430}
431
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700432template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook>
433inline void
Alexander Afanasyevb0c43892012-06-13 00:52:58 -0700434trie<FullKey, Payload, PayloadTraits, PolicyHook>
435::PrintStat (std::ostream &os) const
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700436{
437 os << "# " << key_ << ((payload_ != 0)?"*":"") << ": " << children_.size() << " children" << std::endl;
438 for (size_t bucket = 0, maxbucket = children_.bucket_count ();
439 bucket < maxbucket;
440 bucket++)
441 {
442 os << " " << children_.bucket_size (bucket);
443 }
444 os << "\n";
445
446 typedef trie<FullKey, Payload, PayloadTraits, PolicyHook> trie;
Alexander Afanasyev051d3782012-07-03 10:10:15 -0700447 for (typename trie::unordered_set::const_iterator subnode = children_.begin ();
448 subnode != children_.end ();
449 subnode++ )
450 // BOOST_FOREACH (const trie &subnode, children_)
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700451 {
Alexander Afanasyev051d3782012-07-03 10:10:15 -0700452 subnode->PrintStat (os);
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700453 }
454}
455
456
457template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook>
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700458inline bool
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700459operator == (const trie<FullKey, Payload, PayloadTraits, PolicyHook> &a,
460 const trie<FullKey, Payload, PayloadTraits, PolicyHook> &b)
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700461{
462 return a.key_ == b.key_;
463}
464
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700465template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook>
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700466inline std::size_t
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700467hash_value (const trie<FullKey, Payload, PayloadTraits, PolicyHook> &trie_node)
Alexander Afanasyevfd0c41c2012-06-11 22:15:49 -0700468{
469 return boost::hash_value (trie_node.key_);
470}
Alexander Afanasyev89fb5352012-06-12 22:43:16 -0700471
Alexander Afanasyev9a989702012-06-29 17:44:00 -0700472#endif // TRIE_H_