NS-3 based Named Data Networking (NDN) simulator
ndnSIM: NDN, CCN, CCNx, content centric networks
API Documentation
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
trie.h
1 /* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2011 University of California, Los Angeles
4  *
5  * This program is free software; you can redistribute it and/or modify
6  * it under the terms of the GNU General Public License version 2 as
7  * published by the Free Software Foundation;
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software
16  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17  *
18  * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
19  */
20 
21 #ifndef TRIE_H_
22 #define TRIE_H_
23 
24 #include "ns3/ptr.h"
25 
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>
34 
35 namespace ns3 {
36 namespace ndn {
37 namespace ndnSIM {
38 
40 // Allow customization for payload
41 //
42 template<typename Payload, typename BasePayload = Payload>
44 {
45  typedef Payload payload_type; // general type of the payload
46  typedef Payload* storage_type; // how the payload is actually stored
47  typedef Payload* insert_type; // what parameter is inserted
48 
49  typedef Payload* return_type; // what is returned on access
50  typedef const Payload* const_return_type; // what is returned on const access
51 
52  typedef BasePayload* base_type; // base type of the entry (when implementation details need to be hidden)
53  typedef const BasePayload* const_base_type; // const base type of the entry (when implementation details need to be hidden)
54 
55  static Payload* empty_payload;
56 };
57 
58 template<typename Payload, typename BasePayload>
59 Payload*
61 
62 template<typename Payload, typename BasePayload = Payload>
64 {
65  typedef Payload payload_type;
66  typedef ns3::Ptr<Payload> storage_type;
67  typedef ns3::Ptr<Payload> insert_type;
68 
69  typedef ns3::Ptr<Payload> return_type;
70  typedef ns3::Ptr<const Payload> const_return_type;
71 
72  typedef ns3::Ptr<BasePayload> base_type;
73  typedef ns3::Ptr<const BasePayload> const_base_type;
74 
75  static ns3::Ptr<Payload> empty_payload;
76 };
77 
78 template<typename Payload, typename BasePayload>
79 ns3::Ptr<Payload>
81 
82 template<typename Payload, typename BasePayload = Payload>
84 {
85  typedef Payload payload_type;
86  typedef Payload storage_type;
87  typedef const Payload & insert_type; // nothing to insert
88 
89  typedef Payload& return_type;
90  typedef const Payload & const_return_type;
91 
92  typedef BasePayload& base_type;
93  typedef const BasePayload& const_base_type;
94 
95  static Payload empty_payload;
96 };
97 
98 template<typename Payload, typename BasePayload>
99 Payload
101 
102 
104 // forward declarations
105 //
106 template<typename FullKey,
107  typename PayloadTraits,
108  typename PolicyHook >
109 class trie;
110 
111 template<typename FullKey, typename PayloadTraits, typename PolicyHook>
112 inline std::ostream&
113 operator << (std::ostream &os,
115 
116 template<typename FullKey, typename PayloadTraits, typename PolicyHook>
117 bool
118 operator== (const trie<FullKey, PayloadTraits, PolicyHook> &a,
120 
121 template<typename FullKey, typename PayloadTraits, typename PolicyHook >
122 std::size_t
123 hash_value (const trie<FullKey, PayloadTraits, PolicyHook> &trie_node);
124 
126 // actual definition
127 //
128 template<class T, class NonConstT>
130 
131 template<class T>
133 
134 template<typename FullKey,
135  typename PayloadTraits,
136  typename PolicyHook >
137 class trie
138 {
139 public:
140  typedef typename FullKey::partial_type Key;
141 
142  typedef trie* iterator;
143  typedef const trie* const_iterator;
144 
145  typedef trie_iterator<trie, trie> recursive_iterator;
146  typedef trie_iterator<const trie, trie> const_recursive_iterator;
147 
148  typedef trie_point_iterator<trie> point_iterator;
149  typedef trie_point_iterator<const trie> const_point_iterator;
150 
151  typedef PayloadTraits payload_traits;
152 
153  inline
154  trie (const Key &key, size_t bucketSize = 1, size_t bucketIncrement = 1)
155  : key_ (key)
156  , initialBucketSize_ (bucketSize)
157  , bucketIncrement_ (bucketIncrement)
158  , bucketSize_ (initialBucketSize_)
159  , buckets_ (new bucket_type [bucketSize_]) //cannot use normal pointer, because lifetime of buckets should be larger than lifetime of the container
160  , children_ (bucket_traits (buckets_.get (), bucketSize_))
161  , payload_ (PayloadTraits::empty_payload)
162  , parent_ (0)
163  {
164  }
165 
166  inline
167  ~trie ()
168  {
169  payload_ = PayloadTraits::empty_payload; // necessary for smart pointers...
170  children_.clear_and_dispose (trie_delete_disposer ());
171  }
172 
173  void
174  clear ()
175  {
176  children_.clear_and_dispose (trie_delete_disposer ());
177  }
178 
179  template<class Predicate>
180  void
181  clear_if (Predicate cond)
182  {
183  recursive_iterator trieNode (this);
184  recursive_iterator end (0);
185 
186  while (trieNode != end)
187  {
188  if (cond (*trieNode))
189  {
190  trieNode = recursive_iterator (trieNode->erase ());
191  }
192  trieNode ++;
193  }
194  }
195 
196  // actual entry
197  friend bool
198  operator== <> (const trie<FullKey, PayloadTraits, PolicyHook> &a,
199  const trie<FullKey, PayloadTraits, PolicyHook> &b);
200 
201  friend std::size_t
202  hash_value <> (const trie<FullKey, PayloadTraits, PolicyHook> &trie_node);
203 
204  inline std::pair<iterator, bool>
205  insert (const FullKey &key,
206  typename PayloadTraits::insert_type payload)
207  {
208  trie *trieNode = this;
209 
210  BOOST_FOREACH (const Key &subkey, key)
211  {
212  typename unordered_set::iterator item = trieNode->children_.find (subkey);
213  if (item == trieNode->children_.end ())
214  {
215  trie *newNode = new trie (subkey, initialBucketSize_, bucketIncrement_);
216  // std::cout << "new " << newNode << "\n";
217  newNode->parent_ = trieNode;
218 
219  if (trieNode->children_.size () >= trieNode->bucketSize_)
220  {
221  trieNode->bucketSize_ += trieNode->bucketIncrement_;
222  trieNode->bucketIncrement_ *= 2; // increase bucketIncrement exponentially
223 
224  buckets_array newBuckets (new bucket_type [trieNode->bucketSize_]);
225  trieNode->children_.rehash (bucket_traits (newBuckets.get (), trieNode->bucketSize_));
226  trieNode->buckets_.swap (newBuckets);
227  }
228 
229  std::pair< typename unordered_set::iterator, bool > ret =
230  trieNode->children_.insert (*newNode);
231 
232  trieNode = &(*ret.first);
233  }
234  else
235  trieNode = &(*item);
236  }
237 
238  if (trieNode->payload_ == PayloadTraits::empty_payload)
239  {
240  trieNode->payload_ = payload;
241  return std::make_pair (trieNode, true);
242  }
243  else
244  return std::make_pair (trieNode, false);
245  }
246 
250  inline iterator
251  erase ()
252  {
253  payload_ = PayloadTraits::empty_payload;
254  return prune ();
255  }
256 
260  inline iterator
261  prune ()
262  {
263  if (payload_ == PayloadTraits::empty_payload &&
264  children_.size () == 0)
265  {
266  if (parent_ == 0) return this;
267 
268  trie *parent = parent_;
269  parent->children_.erase_and_dispose (*this, trie_delete_disposer ()); // delete this; basically, committing a suicide
270 
271  return parent->prune ();
272  }
273  return this;
274  }
275 
279  inline void
281  {
282  if (payload_ == PayloadTraits::empty_payload &&
283  children_.size () == 0)
284  {
285  if (parent_ == 0) return;
286 
287  trie *parent = parent_;
288  parent->children_.erase_and_dispose (*this, trie_delete_disposer ()); // delete this; basically, committing a suicide
289  }
290  }
291 
292  // inline boost::tuple<const iterator, bool, const iterator>
293  // find (const FullKey &key) const
294  // {
295  // return const_cast<trie*> (this)->find (key);
296  // }
297 
304  inline boost::tuple<iterator, bool, iterator>
305  find (const FullKey &key)
306  {
307  trie *trieNode = this;
308  iterator foundNode = (payload_ != PayloadTraits::empty_payload) ? this : 0;
309  bool reachLast = true;
310 
311  BOOST_FOREACH (const Key &subkey, key)
312  {
313  typename unordered_set::iterator item = trieNode->children_.find (subkey);
314  if (item == trieNode->children_.end ())
315  {
316  reachLast = false;
317  break;
318  }
319  else
320  {
321  trieNode = &(*item);
322 
323  if (trieNode->payload_ != PayloadTraits::empty_payload)
324  foundNode = trieNode;
325  }
326  }
327 
328  return boost::make_tuple (foundNode, reachLast, trieNode);
329  }
330 
337  template<class Predicate>
338  inline boost::tuple<iterator, bool, iterator>
339  find_if (const FullKey &key, Predicate pred)
340  {
341  trie *trieNode = this;
342  iterator foundNode = (payload_ != PayloadTraits::empty_payload) ? this : 0;
343  bool reachLast = true;
344 
345  BOOST_FOREACH (const Key &subkey, key)
346  {
347  typename unordered_set::iterator item = trieNode->children_.find (subkey);
348  if (item == trieNode->children_.end ())
349  {
350  reachLast = false;
351  break;
352  }
353  else
354  {
355  trieNode = &(*item);
356 
357  if (trieNode->payload_ != PayloadTraits::empty_payload &&
358  pred (trieNode->payload_))
359  {
360  foundNode = trieNode;
361  }
362  }
363  }
364 
365  return boost::make_tuple (foundNode, reachLast, trieNode);
366  }
367 
372  inline iterator
373  find ()
374  {
375  if (payload_ != PayloadTraits::empty_payload)
376  return this;
377 
379  for (typename trie::unordered_set::iterator subnode = children_.begin ();
380  subnode != children_.end ();
381  subnode++ )
382  // BOOST_FOREACH (trie &subnode, children_)
383  {
384  iterator value = subnode->find ();
385  if (value != 0)
386  return value;
387  }
388 
389  return 0;
390  }
391 
397  template<class Predicate>
398  inline const iterator
399  find_if (Predicate pred)
400  {
401  if (payload_ != PayloadTraits::empty_payload && pred (payload_))
402  return this;
403 
405  for (typename trie::unordered_set::iterator subnode = children_.begin ();
406  subnode != children_.end ();
407  subnode++ )
408  // BOOST_FOREACH (const trie &subnode, children_)
409  {
410  iterator value = subnode->find_if (pred);
411  if (value != 0)
412  return value;
413  }
414 
415  return 0;
416  }
417 
426  template<class Predicate>
427  inline const iterator
428  find_if_next_level (Predicate pred)
429  {
431  for (typename trie::unordered_set::iterator subnode = children_.begin ();
432  subnode != children_.end ();
433  subnode++ )
434  {
435  if (pred (subnode->key ()))
436  {
437  return subnode->find ();
438  }
439  }
440 
441  return 0;
442  }
443 
444  iterator end ()
445  {
446  return 0;
447  }
448 
449  const_iterator end () const
450  {
451  return 0;
452  }
453 
454  typename PayloadTraits::const_return_type
455  payload () const
456  {
457  return payload_;
458  }
459 
460  typename PayloadTraits::return_type
461  payload ()
462  {
463  return payload_;
464  }
465 
466  void
467  set_payload (typename PayloadTraits::insert_type payload)
468  {
469  payload_ = payload;
470  }
471 
472  Key key () const
473  {
474  return key_;
475  }
476 
477  inline void
478  PrintStat (std::ostream &os) const;
479 
480 private:
481  //The disposer object function
482  struct trie_delete_disposer
483  {
484  void operator() (trie *delete_this)
485  {
486  delete delete_this;
487  }
488  };
489 
490  template<class D>
491  struct array_disposer
492  {
493  void operator() (D *array)
494  {
495  delete [] array;
496  }
497  };
498 
499  friend
500  std::ostream&
501  operator<< < > (std::ostream &os, const trie &trie_node);
502 
503 public:
504  PolicyHook policy_hook_;
505 
506 private:
507  boost::intrusive::unordered_set_member_hook<> unordered_set_member_hook_;
508 
509  // necessary typedefs
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;
514 
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;
518 
519  template<class T, class NonConstT>
520  friend class trie_iterator;
521 
522  template<class T>
523  friend class trie_point_iterator;
524 
526  // Actual data
528 
529  Key key_;
530 
531  size_t initialBucketSize_;
532  size_t bucketIncrement_;
533 
534  size_t bucketSize_;
535  typedef boost::interprocess::unique_ptr< bucket_type, array_disposer<bucket_type> > buckets_array;
536  buckets_array buckets_;
537  unordered_set children_;
538 
539  typename PayloadTraits::storage_type payload_;
540  trie *parent_; // to make cleaning effective
541 };
542 
543 
544 
545 
546 template<typename FullKey, typename PayloadTraits, typename PolicyHook>
547 inline std::ostream&
548 operator << (std::ostream &os, const trie<FullKey, PayloadTraits, PolicyHook> &trie_node)
549 {
550  os << "# " << trie_node.key_ << ((trie_node.payload_ != PayloadTraits::empty_payload)?"*":"") << std::endl;
551  typedef trie<FullKey, PayloadTraits, PolicyHook> trie;
552 
553  for (typename trie::unordered_set::const_iterator subnode = trie_node.children_.begin ();
554  subnode != trie_node.children_.end ();
555  subnode++ )
556  // BOOST_FOREACH (const trie &subnode, trie_node.children_)
557  {
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";
560 
561  os << "\"" << &trie_node << "\"" << " -> " << "\"" << &(*subnode) << "\"" << "\n";
562  os << *subnode;
563  }
564 
565  return os;
566 }
567 
568 template<typename FullKey, typename PayloadTraits, typename PolicyHook>
569 inline void
570 trie<FullKey, PayloadTraits, PolicyHook>
571 ::PrintStat (std::ostream &os) const
572 {
573  os << "# " << key_ << ((payload_ != PayloadTraits::empty_payload)?"*":"") << ": " << children_.size() << " children" << std::endl;
574  for (size_t bucket = 0, maxbucket = children_.bucket_count ();
575  bucket < maxbucket;
576  bucket++)
577  {
578  os << " " << children_.bucket_size (bucket);
579  }
580  os << "\n";
581 
582  typedef trie<FullKey, PayloadTraits, PolicyHook> trie;
583  for (typename trie::unordered_set::const_iterator subnode = children_.begin ();
584  subnode != children_.end ();
585  subnode++ )
586  // BOOST_FOREACH (const trie &subnode, children_)
587  {
588  subnode->PrintStat (os);
589  }
590 }
591 
592 
593 template<typename FullKey, typename PayloadTraits, typename PolicyHook>
594 inline bool
595 operator == (const trie<FullKey, PayloadTraits, PolicyHook> &a,
596  const trie<FullKey, PayloadTraits, PolicyHook> &b)
597 {
598  return a.key_ == b.key_;
599 }
600 
601 template<typename FullKey, typename PayloadTraits, typename PolicyHook>
602 inline std::size_t
603 hash_value (const trie<FullKey, PayloadTraits, PolicyHook> &trie_node)
604 {
605  return boost::hash_value (trie_node.key_);
606 }
607 
608 
609 
610 template<class Trie, class NonConstTrie> // hack for boost < 1.47
611 class trie_iterator
612 {
613 public:
614  trie_iterator () : trie_ (0) {}
615  trie_iterator (typename Trie::iterator item) : trie_ (item) {}
616  trie_iterator (Trie &item) : trie_ (&item) {}
617 
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); }
626 
627  trie_iterator<Trie,NonConstTrie> &
628  operator++ (int)
629  {
630  if (trie_->children_.size () > 0)
631  trie_ = &(*trie_->children_.begin ());
632  else
633  trie_ = goUp ();
634  return *this;
635  }
636 
637  trie_iterator<Trie,NonConstTrie> &
638  operator++ ()
639  {
640  (*this)++;
641  return *this;
642  }
643 
644 private:
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;
648 
649  Trie* goUp ()
650  {
651  if (trie_->parent_ != 0)
652  {
653  // typename Trie::unordered_set::iterator item =
654  set_iterator item = const_cast<NonConstTrie*>(trie_)->parent_->children_.iterator_to (const_cast<NonConstTrie&> (*trie_));
655  item++;
656  if (item != trie_->parent_->children_.end ())
657  {
658  return &(*item);
659  }
660  else
661  {
662  trie_ = trie_->parent_;
663  return goUp ();
664  }
665  }
666  else
667  return 0;
668  }
669 private:
670  Trie *trie_;
671 };
672 
673 
674 template<class Trie>
675 class trie_point_iterator
676 {
677 private:
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;
681 
682 public:
683  trie_point_iterator () : trie_ (0) {}
684  trie_point_iterator (typename Trie::iterator item) : trie_ (item) {}
685  trie_point_iterator (Trie &item)
686  {
687  if (item.children_.size () != 0)
688  trie_ = &*item.children_.begin ();
689  else
690  trie_ = 0;
691  }
692 
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); }
701 
702  trie_point_iterator<Trie> &
703  operator++ (int)
704  {
705  if (trie_->parent_ != 0)
706  {
707  set_iterator item = trie_->parent_->children_.iterator_to (*trie_);
708  item ++;
709  if (item == trie_->parent_->children_.end ())
710  trie_ = 0;
711  else
712  trie_ = &*item;
713  }
714  else
715  {
716  trie_ = 0;
717  }
718  return *this;
719  }
720 
721  trie_point_iterator<Trie> &
722  operator++ ()
723  {
724  (*this)++;
725  return *this;
726  }
727 
728 private:
729  Trie *trie_;
730 };
731 
732 
733 } // ndnSIM
734 } // ndn
735 } // ns3
736 
737 #endif // TRIE_H_
boost::tuple< iterator, bool, iterator > find(const FullKey &key)
Perform the longest prefix match.
Definition: trie.h:305
iterator prune()
Do exactly as erase, but without erasing the payload.
Definition: trie.h:261
const iterator find_if_next_level(Predicate pred)
Find next payload of the sub-trie satisfying the predicate.
Definition: trie.h:428
const iterator find_if(Predicate pred)
Find next payload of the sub-trie satisfying the predicate.
Definition: trie.h:399
iterator find()
Find next payload of the sub-trie.
Definition: trie.h:373
boost::tuple< iterator, bool, iterator > find_if(const FullKey &key, Predicate pred)
Perform the longest prefix match satisfying preficate.
Definition: trie.h:339
void prune_node()
Perform prune of the node, but without attempting to parent of the node.
Definition: trie.h:280
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. ...
Definition: trie.h:251