26 #include <boost/intrusive/unordered_set.hpp>
27 #include <boost/intrusive/list.hpp>
28 #include <boost/intrusive/set.hpp>
29 #include <boost/functional/hash.hpp>
30 #include <boost/interprocess/smart_ptr/unique_ptr.hpp>
31 #include <boost/tuple/tuple.hpp>
32 #include <boost/foreach.hpp>
33 #include <boost/mpl/if.hpp>
42 template<
typename Payload,
typename BasePayload = Payload>
45 typedef Payload payload_type;
46 typedef Payload* storage_type;
47 typedef Payload* insert_type;
49 typedef Payload* return_type;
50 typedef const Payload* const_return_type;
52 typedef BasePayload* base_type;
53 typedef const BasePayload* const_base_type;
55 static Payload* empty_payload;
58 template<
typename Payload,
typename BasePayload>
62 template<
typename Payload,
typename BasePayload = Payload>
65 typedef Payload payload_type;
66 typedef ns3::Ptr<Payload> storage_type;
67 typedef ns3::Ptr<Payload> insert_type;
69 typedef ns3::Ptr<Payload> return_type;
70 typedef ns3::Ptr<const Payload> const_return_type;
72 typedef ns3::Ptr<BasePayload> base_type;
73 typedef ns3::Ptr<const BasePayload> const_base_type;
75 static ns3::Ptr<Payload> empty_payload;
78 template<
typename Payload,
typename BasePayload>
82 template<
typename Payload,
typename BasePayload = Payload>
85 typedef Payload payload_type;
86 typedef Payload storage_type;
87 typedef const Payload & insert_type;
89 typedef Payload& return_type;
90 typedef const Payload & const_return_type;
92 typedef BasePayload& base_type;
93 typedef const BasePayload& const_base_type;
95 static Payload empty_payload;
98 template<
typename Payload,
typename BasePayload>
106 template<
typename FullKey,
107 typename PayloadTraits,
108 typename PolicyHook >
111 template<
typename FullKey,
typename PayloadTraits,
typename PolicyHook>
113 operator << (std::ostream &os,
116 template<
typename FullKey,
typename PayloadTraits,
typename PolicyHook>
121 template<
typename FullKey,
typename PayloadTraits,
typename PolicyHook >
128 template<
class T,
class NonConstT>
134 template<
typename FullKey,
135 typename PayloadTraits,
136 typename PolicyHook >
140 typedef typename FullKey::partial_type Key;
142 typedef trie* iterator;
143 typedef const trie* const_iterator;
151 typedef PayloadTraits payload_traits;
154 trie (
const Key &key,
size_t bucketSize = 1,
size_t bucketIncrement = 1)
156 , initialBucketSize_ (bucketSize)
157 , bucketIncrement_ (bucketIncrement)
158 , bucketSize_ (initialBucketSize_)
159 , buckets_ (new bucket_type [bucketSize_])
160 , children_ (bucket_traits (buckets_.get (), bucketSize_))
161 , payload_ (PayloadTraits::empty_payload)
169 payload_ = PayloadTraits::empty_payload;
170 children_.clear_and_dispose (trie_delete_disposer ());
176 children_.clear_and_dispose (trie_delete_disposer ());
179 template<
class Predicate>
181 clear_if (Predicate cond)
183 recursive_iterator trieNode (
this);
184 recursive_iterator end (0);
186 while (trieNode != end)
188 if (cond (*trieNode))
190 trieNode = recursive_iterator (trieNode->erase ());
198 operator== <> (
const trie<FullKey, PayloadTraits, PolicyHook> &a,
199 const trie<FullKey, PayloadTraits, PolicyHook> &b);
202 hash_value <> (
const trie<FullKey, PayloadTraits, PolicyHook> &trie_node);
204 inline std::pair<iterator, bool>
205 insert (
const FullKey &key,
206 typename PayloadTraits::insert_type payload)
208 trie *trieNode =
this;
210 BOOST_FOREACH (
const Key &subkey, key)
212 typename unordered_set::iterator item = trieNode->children_.find (subkey);
213 if (item == trieNode->children_.end ())
215 trie *newNode =
new trie (subkey, initialBucketSize_, bucketIncrement_);
217 newNode->parent_ = trieNode;
219 if (trieNode->children_.size () >= trieNode->bucketSize_)
221 trieNode->bucketSize_ += trieNode->bucketIncrement_;
222 trieNode->bucketIncrement_ *= 2;
224 buckets_array newBuckets (
new bucket_type [trieNode->bucketSize_]);
225 trieNode->children_.rehash (bucket_traits (newBuckets.get (), trieNode->bucketSize_));
226 trieNode->buckets_.swap (newBuckets);
229 std::pair< typename unordered_set::iterator, bool > ret =
230 trieNode->children_.insert (*newNode);
232 trieNode = &(*ret.first);
238 if (trieNode->payload_ == PayloadTraits::empty_payload)
240 trieNode->payload_ = payload;
241 return std::make_pair (trieNode,
true);
244 return std::make_pair (trieNode,
false);
253 payload_ = PayloadTraits::empty_payload;
263 if (payload_ == PayloadTraits::empty_payload &&
264 children_.size () == 0)
266 if (parent_ == 0)
return this;
268 trie *parent = parent_;
269 parent->children_.erase_and_dispose (*
this, trie_delete_disposer ());
271 return parent->
prune ();
282 if (payload_ == PayloadTraits::empty_payload &&
283 children_.size () == 0)
285 if (parent_ == 0)
return;
287 trie *parent = parent_;
288 parent->children_.erase_and_dispose (*
this, trie_delete_disposer ());
304 inline boost::tuple<iterator, bool, iterator>
307 trie *trieNode =
this;
308 iterator foundNode = (payload_ != PayloadTraits::empty_payload) ?
this : 0;
309 bool reachLast =
true;
311 BOOST_FOREACH (
const Key &subkey, key)
313 typename unordered_set::iterator item = trieNode->children_.find (subkey);
314 if (item == trieNode->children_.end ())
323 if (trieNode->payload_ != PayloadTraits::empty_payload)
324 foundNode = trieNode;
328 return boost::make_tuple (foundNode, reachLast, trieNode);
337 template<
class Predicate>
338 inline boost::tuple<iterator, bool, iterator>
341 trie *trieNode =
this;
342 iterator foundNode = (payload_ != PayloadTraits::empty_payload) ?
this : 0;
343 bool reachLast =
true;
345 BOOST_FOREACH (
const Key &subkey, key)
347 typename unordered_set::iterator item = trieNode->children_.find (subkey);
348 if (item == trieNode->children_.end ())
357 if (trieNode->payload_ != PayloadTraits::empty_payload &&
358 pred (trieNode->payload_))
360 foundNode = trieNode;
365 return boost::make_tuple (foundNode, reachLast, trieNode);
375 if (payload_ != PayloadTraits::empty_payload)
379 for (
typename trie::unordered_set::iterator subnode = children_.begin ();
380 subnode != children_.end ();
397 template<
class Predicate>
398 inline const iterator
401 if (payload_ != PayloadTraits::empty_payload && pred (payload_))
405 for (
typename trie::unordered_set::iterator subnode = children_.begin ();
406 subnode != children_.end ();
426 template<
class Predicate>
427 inline const iterator
431 for (
typename trie::unordered_set::iterator subnode = children_.begin ();
432 subnode != children_.end ();
435 if (pred (subnode->key ()))
437 return subnode->
find ();
449 const_iterator end ()
const
454 typename PayloadTraits::const_return_type
460 typename PayloadTraits::return_type
467 set_payload (
typename PayloadTraits::insert_type payload)
478 PrintStat (std::ostream &os)
const;
482 struct trie_delete_disposer
484 void operator() (trie *delete_this)
491 struct array_disposer
493 void operator() (D *array)
501 operator<< < > (std::ostream &os,
const trie &trie_node);
504 PolicyHook policy_hook_;
507 boost::intrusive::unordered_set_member_hook<> unordered_set_member_hook_;
510 typedef trie self_type;
511 typedef boost::intrusive::member_hook< trie,
512 boost::intrusive::unordered_set_member_hook< >,
513 &trie::unordered_set_member_hook_ > member_hook;
515 typedef boost::intrusive::unordered_set< trie, member_hook > unordered_set;
516 typedef typename unordered_set::bucket_type bucket_type;
517 typedef typename unordered_set::bucket_traits bucket_traits;
519 template<
class T,
class NonConstT>
520 friend class trie_iterator;
523 friend class trie_point_iterator;
531 size_t initialBucketSize_;
532 size_t bucketIncrement_;
535 typedef boost::interprocess::unique_ptr< bucket_type, array_disposer<bucket_type> > buckets_array;
536 buckets_array buckets_;
537 unordered_set children_;
539 typename PayloadTraits::storage_type payload_;
546 template<
typename FullKey,
typename PayloadTraits,
typename PolicyHook>
548 operator << (std::ostream &os, const trie<FullKey, PayloadTraits, PolicyHook> &trie_node)
550 os <<
"# " << trie_node.key_ << ((trie_node.payload_ != PayloadTraits::empty_payload)?
"*":
"") << std::endl;
551 typedef trie<FullKey, PayloadTraits, PolicyHook> trie;
553 for (
typename trie::unordered_set::const_iterator subnode = trie_node.children_.begin ();
554 subnode != trie_node.children_.end ();
558 os <<
"\"" << &trie_node <<
"\"" <<
" [label=\"" << trie_node.key_ << ((trie_node.payload_ != PayloadTraits::empty_payload)?
"*":
"") <<
"\"]\n";
559 os <<
"\"" << &(*subnode) <<
"\"" <<
" [label=\"" << subnode->key_ << ((subnode->payload_ != PayloadTraits::empty_payload)?
"*":
"") <<
"\"]""\n";
561 os <<
"\"" << &trie_node <<
"\"" <<
" -> " <<
"\"" << &(*subnode) <<
"\"" <<
"\n";
568 template<
typename FullKey,
typename PayloadTraits,
typename PolicyHook>
570 trie<FullKey, PayloadTraits, PolicyHook>
571 ::PrintStat (std::ostream &os)
const
573 os <<
"# " << key_ << ((payload_ != PayloadTraits::empty_payload)?
"*":
"") <<
": " << children_.size() <<
" children" << std::endl;
574 for (
size_t bucket = 0, maxbucket = children_.bucket_count ();
578 os <<
" " << children_.bucket_size (bucket);
582 typedef trie<FullKey, PayloadTraits, PolicyHook> trie;
583 for (
typename trie::unordered_set::const_iterator subnode = children_.begin ();
584 subnode != children_.end ();
588 subnode->PrintStat (os);
593 template<
typename FullKey,
typename PayloadTraits,
typename PolicyHook>
595 operator == (
const trie<FullKey, PayloadTraits, PolicyHook> &a,
596 const trie<FullKey, PayloadTraits, PolicyHook> &b)
598 return a.key_ == b.key_;
601 template<
typename FullKey,
typename PayloadTraits,
typename PolicyHook>
603 hash_value (
const trie<FullKey, PayloadTraits, PolicyHook> &trie_node)
605 return boost::hash_value (trie_node.key_);
610 template<
class Trie,
class NonConstTrie>
614 trie_iterator () : trie_ (0) {}
615 trie_iterator (
typename Trie::iterator item) : trie_ (item) {}
616 trie_iterator (Trie &item) : trie_ (&item) {}
618 Trie & operator* () {
return *trie_; }
619 const Trie & operator* ()
const {
return *trie_; }
620 Trie * operator-> () {
return trie_; }
621 const Trie * operator-> ()
const {
return trie_; }
622 bool operator== (trie_iterator<const Trie, NonConstTrie> &other)
const {
return (trie_ == other.trie_); }
623 bool operator== (trie_iterator<Trie, NonConstTrie> &other) {
return (trie_ == other.trie_); }
624 bool operator!= (trie_iterator<const Trie, NonConstTrie> &other)
const {
return !(*
this == other); }
625 bool operator!= (trie_iterator<Trie, NonConstTrie> &other) {
return !(*
this == other); }
627 trie_iterator<Trie,NonConstTrie> &
630 if (trie_->children_.size () > 0)
631 trie_ = &(*trie_->children_.begin ());
637 trie_iterator<Trie,NonConstTrie> &
645 typedef typename boost::mpl::if_< boost::is_same<Trie, NonConstTrie>,
646 typename Trie::unordered_set::iterator,
647 typename Trie::unordered_set::const_iterator>::type set_iterator;
651 if (trie_->parent_ != 0)
654 set_iterator item =
const_cast<NonConstTrie*
>(trie_)->parent_->children_.iterator_to (const_cast<NonConstTrie&> (*trie_));
656 if (item != trie_->parent_->children_.end ())
662 trie_ = trie_->parent_;
675 class trie_point_iterator
678 typedef typename boost::mpl::if_< boost::is_same<Trie, const Trie>,
679 typename Trie::unordered_set::const_iterator,
680 typename Trie::unordered_set::iterator>::type set_iterator;
683 trie_point_iterator () : trie_ (0) {}
684 trie_point_iterator (
typename Trie::iterator item) : trie_ (item) {}
685 trie_point_iterator (Trie &item)
687 if (item.children_.size () != 0)
688 trie_ = &*item.children_.begin ();
693 Trie & operator* () {
return *trie_; }
694 const Trie & operator* ()
const {
return *trie_; }
695 Trie * operator-> () {
return trie_; }
696 const Trie * operator-> ()
const {
return trie_; }
697 bool operator== (trie_point_iterator<const Trie> &other)
const {
return (trie_ == other.trie_); }
698 bool operator== (trie_point_iterator<Trie> &other) {
return (trie_ == other.trie_); }
699 bool operator!= (trie_point_iterator<const Trie> &other)
const {
return !(*
this == other); }
700 bool operator!= (trie_point_iterator<Trie> &other) {
return !(*
this == other); }
702 trie_point_iterator<Trie> &
705 if (trie_->parent_ != 0)
707 set_iterator item = trie_->parent_->children_.iterator_to (*trie_);
709 if (item == trie_->parent_->children_.end ())
721 trie_point_iterator<Trie> &
boost::tuple< iterator, bool, iterator > find(const FullKey &key)
Perform the longest prefix match.
iterator prune()
Do exactly as erase, but without erasing the payload.
const iterator find_if_next_level(Predicate pred)
Find next payload of the sub-trie satisfying the predicate.
const iterator find_if(Predicate pred)
Find next payload of the sub-trie satisfying the predicate.
iterator find()
Find next payload of the sub-trie.
boost::tuple< iterator, bool, iterator > find_if(const FullKey &key, Predicate pred)
Perform the longest prefix match satisfying preficate.
void prune_node()
Perform prune of the node, but without attempting to parent of the node.
Class to representing binary blob of NDN name component.
iterator erase()
Removes payload (if it exists) and if there are no children, prunes parents trie. ...