NS-3 based Named Data Networking (NDN) simulator
ndnSIM 2.5: NDN, CCN, CCNx, content centric networks
API Documentation
trie.hpp
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
20 #ifndef TRIE_H_
21 #define TRIE_H_
22 
24 
25 #include "ns3/ndnSIM/model/ndn-common.hpp"
26 
27 #include "ns3/ptr.h"
28 
29 #include <boost/intrusive/unordered_set.hpp>
30 #include <boost/intrusive/list.hpp>
31 #include <boost/intrusive/set.hpp>
32 #include <boost/functional/hash.hpp>
33 #include <boost/interprocess/smart_ptr/unique_ptr.hpp>
34 #include <tuple>
35 #include <boost/foreach.hpp>
36 #include <boost/mpl/if.hpp>
37 
38 namespace ns3 {
39 namespace ndn {
40 namespace ndnSIM {
41 
43 // Allow customization for payload
44 //
45 template<typename Payload, typename BasePayload = Payload>
46 struct pointer_payload_traits {
47  typedef Payload payload_type; // general type of the payload
48  typedef Payload* storage_type; // how the payload is actually stored
49  typedef Payload* insert_type; // what parameter is inserted
50 
51  typedef Payload* return_type; // what is returned on access
52  typedef const Payload* const_return_type; // what is returned on const access
53 
54  typedef BasePayload*
55  base_type; // base type of the entry (when implementation details need to be hidden)
56  typedef const BasePayload*
57  const_base_type; // const base type of the entry (when implementation details need to be hidden)
58 
59  static Payload* empty_payload;
60 };
61 
62 template<typename Payload, typename BasePayload>
63 Payload* pointer_payload_traits<Payload, BasePayload>::empty_payload = 0;
64 
65 template<typename Payload, typename BasePayload = Payload>
66 struct smart_pointer_payload_traits {
67  typedef Payload payload_type;
68  typedef ns3::Ptr<Payload> storage_type;
69  typedef ns3::Ptr<Payload> insert_type;
70 
71  typedef ns3::Ptr<Payload> return_type;
72  typedef ns3::Ptr<const Payload> const_return_type;
73 
74  typedef ns3::Ptr<BasePayload> base_type;
75  typedef ns3::Ptr<const BasePayload> const_base_type;
76 
77  static ns3::Ptr<Payload> empty_payload;
78 };
79 
80 template<typename Payload, typename BasePayload>
81 ns3::Ptr<Payload> smart_pointer_payload_traits<Payload, BasePayload>::empty_payload = 0;
82 
83 template<typename Payload, typename BasePayload = Payload>
84 struct non_pointer_traits {
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 non_pointer_traits<Payload, BasePayload>::empty_payload = Payload();
100 
102 // forward declarations
103 //
104 template<typename FullKey, typename PayloadTraits, typename PolicyHook>
105 class trie;
106 
107 template<typename FullKey, typename PayloadTraits, typename PolicyHook>
108 inline std::ostream&
109 operator<<(std::ostream& os, const trie<FullKey, PayloadTraits, PolicyHook>& trie_node);
110 
111 template<typename FullKey, typename PayloadTraits, typename PolicyHook>
112 bool
113 operator==(const trie<FullKey, PayloadTraits, PolicyHook>& a,
114  const trie<FullKey, PayloadTraits, PolicyHook>& b);
115 
116 template<typename FullKey, typename PayloadTraits, typename PolicyHook>
117 std::size_t
118 hash_value(const trie<FullKey, PayloadTraits, PolicyHook>& trie_node);
119 
121 // actual definition
122 //
123 template<class T, class NonConstT>
124 class trie_iterator;
125 
126 template<class T>
127 class trie_point_iterator;
128 
129 template<typename FullKey, typename PayloadTraits, typename PolicyHook>
130 class trie {
131 public:
132  typedef typename FullKey::value_type Key;
133 
134  typedef trie* iterator;
135  typedef const trie* const_iterator;
136 
137  typedef trie_iterator<trie, trie> recursive_iterator;
138  typedef trie_iterator<const trie, trie> const_recursive_iterator;
139 
140  typedef trie_point_iterator<trie> point_iterator;
141  typedef trie_point_iterator<const trie> const_point_iterator;
142 
143  typedef PayloadTraits payload_traits;
144 
145  inline trie(const Key& key, size_t bucketSize = 1, size_t bucketIncrement = 1)
146  : key_(key)
147  , initialBucketSize_(bucketSize)
148  , bucketIncrement_(bucketIncrement)
149  , bucketSize_(initialBucketSize_)
150  , buckets_(new bucket_type[bucketSize_]) // cannot use normal pointer, because lifetime of
151  // buckets should be larger than lifetime of the
152  // container
153  , children_(bucket_traits(buckets_.get(), bucketSize_))
154  , payload_(PayloadTraits::empty_payload)
155  , parent_(nullptr)
156  {
157  }
158 
159  inline ~trie()
160  {
161  payload_ = PayloadTraits::empty_payload; // necessary for smart pointers...
162  children_.clear_and_dispose(trie_delete_disposer());
163  }
164 
165  void
166  clear()
167  {
168  children_.clear_and_dispose(trie_delete_disposer());
169  }
170 
171  template<class Predicate>
172  void
173  clear_if(Predicate cond)
174  {
175  recursive_iterator trieNode(this);
176  recursive_iterator end(0);
177 
178  while (trieNode != end) {
179  if (cond(*trieNode)) {
180  trieNode = recursive_iterator(trieNode->erase());
181  }
182  trieNode++;
183  }
184  }
185 
186  // actual entry
187  friend bool operator==<>(const trie<FullKey, PayloadTraits, PolicyHook>& a,
188  const trie<FullKey, PayloadTraits, PolicyHook>& b);
189 
190  friend std::size_t
191  hash_value<>(const trie<FullKey, PayloadTraits, PolicyHook>& trie_node);
192 
193  inline std::pair<iterator, bool>
194  insert(const FullKey& key, typename PayloadTraits::insert_type payload)
195  {
196  trie* trieNode = this;
197 
198  BOOST_FOREACH (const Key& subkey, key) {
199  typename unordered_set::iterator item = trieNode->children_.find(subkey);
200  if (item == trieNode->children_.end()) {
201  trie* newNode = new trie(subkey, initialBucketSize_, bucketIncrement_);
202  // std::cout << "new " << newNode << "\n";
203  newNode->parent_ = trieNode;
204 
205  if (trieNode->children_.size() >= trieNode->bucketSize_) {
206  trieNode->bucketSize_ += trieNode->bucketIncrement_;
207  trieNode->bucketIncrement_ *= 2; // increase bucketIncrement exponentially
208 
209  buckets_array newBuckets(new bucket_type[trieNode->bucketSize_]);
210  trieNode->children_.rehash(bucket_traits(newBuckets.get(), trieNode->bucketSize_));
211  trieNode->buckets_.swap(newBuckets);
212  }
213 
214  std::pair<typename unordered_set::iterator, bool> ret =
215  trieNode->children_.insert(*newNode);
216 
217  trieNode = &(*ret.first);
218  }
219  else
220  trieNode = &(*item);
221  }
222 
223  if (trieNode->payload_ == PayloadTraits::empty_payload) {
224  trieNode->payload_ = payload;
225  return std::make_pair(trieNode, true);
226  }
227  else
228  return std::make_pair(trieNode, false);
229  }
230 
234  inline iterator
235  erase()
236  {
237  payload_ = PayloadTraits::empty_payload;
238  return prune();
239  }
240 
244  inline iterator
245  prune()
246  {
247  if (payload_ == PayloadTraits::empty_payload && children_.size() == 0) {
248  if (parent_ == 0)
249  return this;
250 
251  trie* parent = parent_;
252  parent->children_
253  .erase_and_dispose(*this,
254  trie_delete_disposer()); // delete this; basically, committing a suicide
255 
256  return parent->prune();
257  }
258  return this;
259  }
260 
264  inline void
265  prune_node()
266  {
267  if (payload_ == PayloadTraits::empty_payload && children_.size() == 0) {
268  if (parent_ == 0)
269  return;
270 
271  trie* parent = parent_;
272  parent->children_
273  .erase_and_dispose(*this,
274  trie_delete_disposer()); // delete this; basically, committing a suicide
275  }
276  }
277 
278  // inline std::tuple<const iterator, bool, const iterator>
279  // find (const FullKey &key) const
280  // {
281  // return const_cast<trie*> (this)->find (key);
282  // }
283 
290  inline std::tuple<iterator, bool, iterator>
291  find(const FullKey& key)
292  {
293  trie* trieNode = this;
294  iterator foundNode = (payload_ != PayloadTraits::empty_payload) ? this : 0;
295  bool reachLast = true;
296 
297  BOOST_FOREACH (const Key& subkey, key) {
298  typename unordered_set::iterator item = trieNode->children_.find(subkey);
299  if (item == trieNode->children_.end()) {
300  reachLast = false;
301  break;
302  }
303  else {
304  trieNode = &(*item);
305 
306  if (trieNode->payload_ != PayloadTraits::empty_payload)
307  foundNode = trieNode;
308  }
309  }
310 
311  return std::make_tuple(foundNode, reachLast, trieNode);
312  }
313 
320  template<class Predicate>
321  inline std::tuple<iterator, bool, iterator>
322  find_if(const FullKey& key, Predicate pred)
323  {
324  trie* trieNode = this;
325  iterator foundNode = (payload_ != PayloadTraits::empty_payload) ? this : 0;
326  bool reachLast = true;
327 
328  BOOST_FOREACH (const Key& subkey, key) {
329  typename unordered_set::iterator item = trieNode->children_.find(subkey);
330  if (item == trieNode->children_.end()) {
331  reachLast = false;
332  break;
333  }
334  else {
335  trieNode = &(*item);
336 
337  if (trieNode->payload_ != PayloadTraits::empty_payload && pred(trieNode->payload_)) {
338  foundNode = trieNode;
339  }
340  }
341  }
342 
343  return std::make_tuple(foundNode, reachLast, trieNode);
344  }
345 
351  inline iterator
352  find()
353  {
354  if (payload_ != PayloadTraits::empty_payload)
355  return this;
356 
357  typedef trie<FullKey, PayloadTraits, PolicyHook> trie;
358  for (typename trie::unordered_set::iterator subnode = children_.begin();
359  subnode != children_.end(); subnode++)
360  // BOOST_FOREACH (trie &subnode, children_)
361  {
362  iterator value = subnode->find();
363  if (value != 0)
364  return value;
365  }
366 
367  return 0;
368  }
369 
376  template<class Predicate>
377  inline const iterator
378  find_if(Predicate pred)
379  {
380  if (payload_ != PayloadTraits::empty_payload && pred(payload_))
381  return this;
382 
383  typedef trie<FullKey, PayloadTraits, PolicyHook> trie;
384  for (typename trie::unordered_set::iterator subnode = children_.begin();
385  subnode != children_.end(); subnode++)
386  // BOOST_FOREACH (const trie &subnode, children_)
387  {
388  iterator value = subnode->find_if(pred);
389  if (value != 0)
390  return value;
391  }
392 
393  return 0;
394  }
395 
405  template<class Predicate>
406  inline const iterator
407  find_if_next_level(Predicate pred)
408  {
409  typedef trie<FullKey, PayloadTraits, PolicyHook> trie;
410  for (typename trie::unordered_set::iterator subnode = children_.begin();
411  subnode != children_.end(); subnode++) {
412  if (pred(subnode->key())) {
413  return subnode->find();
414  }
415  }
416 
417  return 0;
418  }
419 
420  iterator
421  end()
422  {
423  return 0;
424  }
425 
426  const_iterator
427  end() const
428  {
429  return 0;
430  }
431 
432  typename PayloadTraits::const_return_type
433  payload() const
434  {
435  return payload_;
436  }
437 
438  typename PayloadTraits::return_type
439  payload()
440  {
441  return payload_;
442  }
443 
444  void
445  set_payload(typename PayloadTraits::insert_type payload)
446  {
447  payload_ = payload;
448  }
449 
450  Key
451  key() const
452  {
453  return key_;
454  }
455 
456  inline void
457  PrintStat(std::ostream& os) const;
458 
459 private:
460  // The disposer object function
461  struct trie_delete_disposer {
462  void
463  operator()(trie* delete_this)
464  {
465  delete delete_this;
466  }
467  };
468 
469  template<class D>
470  struct array_disposer {
471  void
472  operator()(D* array)
473  {
474  delete[] array;
475  }
476  };
477 
478  friend std::ostream& operator<<<>(std::ostream& os, const trie& trie_node);
479 
480 public:
481  PolicyHook policy_hook_;
482 
483 private:
484  boost::intrusive::unordered_set_member_hook<> unordered_set_member_hook_;
485 
486  // necessary typedefs
487  typedef trie self_type;
488  typedef boost::intrusive::member_hook<trie, boost::intrusive::unordered_set_member_hook<>,
489  &trie::unordered_set_member_hook_> member_hook;
490 
491  typedef boost::intrusive::unordered_set<trie, member_hook> unordered_set;
492  typedef typename unordered_set::bucket_type bucket_type;
493  typedef typename unordered_set::bucket_traits bucket_traits;
494 
495  template<class T, class NonConstT>
496  friend class trie_iterator;
497 
498  template<class T>
499  friend class trie_point_iterator;
500 
502  // Actual data
504 
505  Key key_;
506 
507  size_t initialBucketSize_;
508  size_t bucketIncrement_;
509 
510  size_t bucketSize_;
511  typedef boost::interprocess::unique_ptr<bucket_type, array_disposer<bucket_type>> buckets_array;
512  buckets_array buckets_;
513  unordered_set children_;
514 
515  typename PayloadTraits::storage_type payload_;
516  trie* parent_; // to make cleaning effective
517 };
518 
519 template<typename FullKey, typename PayloadTraits, typename PolicyHook>
520 inline std::ostream&
521 operator<<(std::ostream& os, const trie<FullKey, PayloadTraits, PolicyHook>& trie_node)
522 {
523  os << "# " << trie_node.key_ << ((trie_node.payload_ != PayloadTraits::empty_payload) ? "*" : "")
524  << std::endl;
525  typedef trie<FullKey, PayloadTraits, PolicyHook> trie;
526 
527  for (typename trie::unordered_set::const_iterator subnode = trie_node.children_.begin();
528  subnode != trie_node.children_.end(); subnode++)
529  // BOOST_FOREACH (const trie &subnode, trie_node.children_)
530  {
531  os << "\"" << &trie_node << "\""
532  << " [label=\"" << trie_node.key_
533  << ((trie_node.payload_ != PayloadTraits::empty_payload) ? "*" : "") << "\"]\n";
534  os << "\"" << &(*subnode) << "\""
535  << " [label=\"" << subnode->key_
536  << ((subnode->payload_ != PayloadTraits::empty_payload) ? "*" : "") << "\"]"
537  "\n";
538 
539  os << "\"" << &trie_node << "\""
540  << " -> "
541  << "\"" << &(*subnode) << "\""
542  << "\n";
543  os << *subnode;
544  }
545 
546  return os;
547 }
548 
549 template<typename FullKey, typename PayloadTraits, typename PolicyHook>
550 inline void
551 trie<FullKey, PayloadTraits, PolicyHook>::PrintStat(std::ostream& os) const
552 {
553  os << "# " << key_ << ((payload_ != PayloadTraits::empty_payload) ? "*" : "") << ": "
554  << children_.size() << " children" << std::endl;
555  for (size_t bucket = 0, maxbucket = children_.bucket_count(); bucket < maxbucket; bucket++) {
556  os << " " << children_.bucket_size(bucket);
557  }
558  os << "\n";
559 
560  typedef trie<FullKey, PayloadTraits, PolicyHook> trie;
561  for (typename trie::unordered_set::const_iterator subnode = children_.begin();
562  subnode != children_.end(); subnode++)
563  // BOOST_FOREACH (const trie &subnode, children_)
564  {
565  subnode->PrintStat(os);
566  }
567 }
568 
569 template<typename FullKey, typename PayloadTraits, typename PolicyHook>
570 inline bool
571 operator==(const trie<FullKey, PayloadTraits, PolicyHook>& a,
572  const trie<FullKey, PayloadTraits, PolicyHook>& b)
573 {
574  return a.key_ == b.key_;
575 }
576 
577 template<typename FullKey, typename PayloadTraits, typename PolicyHook>
578 inline std::size_t
579 hash_value(const trie<FullKey, PayloadTraits, PolicyHook>& trie_node)
580 {
581  return boost::hash_value(trie_node.key_);
582 }
583 
584 template<class Trie, class NonConstTrie> // hack for boost < 1.47
585 class trie_iterator {
586 public:
587  trie_iterator()
588  : trie_(0)
589  {
590  }
591  trie_iterator(typename Trie::iterator item)
592  : trie_(item)
593  {
594  }
595  trie_iterator(Trie& item)
596  : trie_(&item)
597  {
598  }
599 
600  Trie& operator*()
601  {
602  return *trie_;
603  }
604  const Trie& operator*() const
605  {
606  return *trie_;
607  }
608  Trie* operator->()
609  {
610  return trie_;
611  }
612  const Trie* operator->() const
613  {
614  return trie_;
615  }
616  bool
617  operator==(trie_iterator<const Trie, NonConstTrie>& other) const
618  {
619  return (trie_ == other.trie_);
620  }
621  bool
622  operator==(trie_iterator<Trie, NonConstTrie>& other)
623  {
624  return (trie_ == other.trie_);
625  }
626  bool
627  operator!=(trie_iterator<const Trie, NonConstTrie>& other) const
628  {
629  return !(*this == other);
630  }
631  bool
632  operator!=(trie_iterator<Trie, NonConstTrie>& other)
633  {
634  return !(*this == other);
635  }
636 
637  trie_iterator<Trie, NonConstTrie>&
638  operator++(int)
639  {
640  if (trie_->children_.size() > 0)
641  trie_ = &(*trie_->children_.begin());
642  else
643  trie_ = goUp();
644  return *this;
645  }
646 
647  trie_iterator<Trie, NonConstTrie>&
648  operator++()
649  {
650  (*this)++;
651  return *this;
652  }
653 
654 private:
655  typedef typename boost::mpl::if_<boost::is_same<Trie, NonConstTrie>,
657  typename Trie::unordered_set::const_iterator>::type set_iterator;
658 
659  Trie*
660  goUp()
661  {
662  if (trie_->parent_ != 0) {
663  // typename Trie::unordered_set::iterator item =
664  set_iterator item = const_cast<NonConstTrie*>(trie_)
665  ->parent_->children_.iterator_to(const_cast<NonConstTrie&>(*trie_));
666  item++;
667  if (item != trie_->parent_->children_.end()) {
668  return &(*item);
669  }
670  else {
671  trie_ = trie_->parent_;
672  return goUp();
673  }
674  }
675  else
676  return 0;
677  }
678 
679 private:
680  Trie* trie_;
681 };
682 
683 template<class Trie>
684 class trie_point_iterator {
685 private:
686  typedef typename boost::mpl::if_<boost::is_same<Trie, const Trie>,
687  typename Trie::unordered_set::const_iterator,
688  typename Trie::unordered_set::iterator>::type set_iterator;
689 
690 public:
691  trie_point_iterator()
692  : trie_(0)
693  {
694  }
695  trie_point_iterator(typename Trie::iterator item)
696  : trie_(item)
697  {
698  }
699  trie_point_iterator(Trie& item)
700  {
701  if (item.children_.size() != 0)
702  trie_ = &*item.children_.begin();
703  else
704  trie_ = 0;
705  }
706 
707  Trie& operator*()
708  {
709  return *trie_;
710  }
711  const Trie& operator*() const
712  {
713  return *trie_;
714  }
715  Trie* operator->()
716  {
717  return trie_;
718  }
719  const Trie* operator->() const
720  {
721  return trie_;
722  }
723  bool
724  operator==(trie_point_iterator<const Trie>& other) const
725  {
726  return (trie_ == other.trie_);
727  }
728  bool
729  operator==(trie_point_iterator<Trie>& other)
730  {
731  return (trie_ == other.trie_);
732  }
733  bool
734  operator!=(trie_point_iterator<const Trie>& other) const
735  {
736  return !(*this == other);
737  }
738  bool
739  operator!=(trie_point_iterator<Trie>& other)
740  {
741  return !(*this == other);
742  }
743 
744  trie_point_iterator<Trie>&
745  operator++(int)
746  {
747  if (trie_->parent_ != 0) {
748  set_iterator item = trie_->parent_->children_.iterator_to(*trie_);
749  item++;
750  if (item == trie_->parent_->children_.end())
751  trie_ = 0;
752  else
753  trie_ = &*item;
754  }
755  else {
756  trie_ = 0;
757  }
758  return *this;
759  }
760 
761  trie_point_iterator<Trie>&
762  operator++()
763  {
764  (*this)++;
765  return *this;
766  }
767 
768 private:
769  Trie* trie_;
770 };
771 
772 } // ndnSIM
773 } // ndn
774 } // ns3
775 
777 
778 #endif // TRIE_H_
Copyright (c) 2011-2015 Regents of the University of California.
std::size_t hash_value(const ::ndn::name::Component component)
Table::const_iterator iterator
Definition: cs-internal.hpp:41
Copyright (c) 2011-2015 Regents of the University of California.
bool operator!=(const GlobalRouter::Incidency &a, const GlobalRouter::Incidency &b)
bool operator==(const GlobalRouter::Incidency &a, const GlobalRouter::Incidency &b)