Update trie and adding policy management
diff --git a/examples/trie.cc b/examples/trie.cc
index 4a70a87..36e52ac 100644
--- a/examples/trie.cc
+++ b/examples/trie.cc
@@ -30,43 +30,71 @@
{
public:
Integer (int value) : value_ (value) {}
-
+
+ operator int () const { return value_; }
private:
int value_;
};
+std::ostream &
+operator << (std::ostream &os, const Integer &i)
+{
+ os << (int)i;
+ return os;
+}
+
int
main (int argc, char *argv[])
{
- trie<ns3::CcnxNameComponents, Integer, smart_pointer_payload_traits<Integer> > *x =
- new trie<ns3::CcnxNameComponents, Integer, smart_pointer_payload_traits<Integer> >("root");
-
- ns3::CcnxNameComponents n1,n2,n3,n5;
+ typedef indexed_trie<ns3::CcnxNameComponents, Integer, smart_pointer_payload_traits<Integer> > trie;
+ trie x;
+ x.getPolicy ().set_max_size (2);
+
+ // x.getTrie ().PrintStat (std::cout);
+
+ ns3::CcnxNameComponents n1,n2,n3,n4;
n1("a")("b")("c");
- n2("a")("c");
- n3("b")("c");
- n5("a")("b");
+ n2("a")("b")("d");
+ n3("a")("b")("f");
+ n4("a")("b");
ns3::Ptr<Integer> i = ns3::Create<Integer> (1);
- x->insert (n1, i);
- x->insert (n2, i);
- x->insert (n3, i);
- x->insert (n5, i);
+ x.insert (n4, ns3::Create<Integer> (4));
- ns3::CcnxNameComponents n4;
- n4("a")("c");
+
+
+ x.insert (n3, ns3::Create<Integer> (3));
+
+ std::pair< trie::iterator, bool > item =
+ x.insert (n2, ns3::Create<Integer> (2));
+ x.erase (item.first);
+
+ x.insert (n1, ns3::Create<Integer> (1));
+ x.find (n1);
+ x.insert (n4, ns3::Create<Integer> (4));
+
+ // std::cout << x.getTrie ();
+ BOOST_FOREACH (const trie::parent_trie &item, x.getPolicy ())
+ {
+ std::cout << *item.payload () << " " << std::endl;
+ }
+
+ // ns3::CcnxNameComponents n4;
+ // n4("a")("c");
- // std::cout << *x->find (n4).get<0> ();
+ // // std::cout << *x->find (n4).get<0> ();
- x->prune ();
- // x->find (n5).get<0> ()->erase ();
- x->find (n1).get<0> ()->erase ();
+ // x->prune ();
+ // // x->find (n5).get<0> ()->erase ();
+ // x->find (n1).get<0> ()->erase ();
- std::cout << "digraph trie {\n";
- std::cout << *x;
- std::cout << "}\n";
+ // std::cout << "digraph trie {\n";
+ // std::cout << *x;
+ // std::cout << "}\n";
- delete x;
+ // x->PrintStat (std::cout);
+
+ // delete x;
return 0;
}
diff --git a/utils/trie.h b/utils/trie.h
index 0e1a330..e45ee70 100644
--- a/utils/trie.h
+++ b/utils/trie.h
@@ -22,7 +22,10 @@
#include "ns3/ndnSIM-module.h"
#include <boost/intrusive/unordered_set.hpp>
+#include <boost/intrusive/list.hpp>
#include <boost/functional/hash.hpp>
+#include <boost/interprocess/smart_ptr/unique_ptr.hpp>
+#include <boost/tuple/tuple.hpp>
namespace bi = boost::intrusive;
@@ -59,20 +62,25 @@
////////////////////////////////////////////////////
// forward declarations
//
-template<typename FullKey, typename Payload, typename PayloadTraits = pointer_payload_traits<Payload> >
+template<typename FullKey,
+ typename Payload,
+ typename PayloadTraits = pointer_payload_traits<Payload>,
+ typename PolicyHook = bi::list_member_hook<> >
class trie;
-template<typename FullKey, typename Payload, typename PayloadTraits>
+template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook>
inline std::ostream&
-operator << (std::ostream &os, const trie<FullKey, Payload, PayloadTraits> &trie_node);
+operator << (std::ostream &os,
+ const trie<FullKey, Payload, PayloadTraits, PolicyHook> &trie_node);
-template<typename FullKey, typename Payload, typename PayloadTraits>
+template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook>
bool
-operator== (const trie<FullKey, Payload, PayloadTraits> &a, const trie<FullKey, Payload, PayloadTraits> &b);
+operator== (const trie<FullKey, Payload, PayloadTraits, PolicyHook> &a,
+ const trie<FullKey, Payload, PayloadTraits, PolicyHook> &b);
-template<typename FullKey, typename Payload, typename PayloadTraits >
+template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook >
std::size_t
-hash_value (const trie<FullKey, Payload, PayloadTraits> &trie_node);
+hash_value (const trie<FullKey, Payload, PayloadTraits, PolicyHook> &trie_node);
///////////////////////////////////////////////////
// actual definition
@@ -80,7 +88,8 @@
template<typename FullKey,
- typename Payload, typename PayloadTraits>
+ typename Payload, typename PayloadTraits,
+ typename PolicyHook >
class trie
{
public:
@@ -97,13 +106,15 @@
// actual entry
friend bool
- operator== <> (const trie<FullKey, Payload, PayloadTraits> &a, const trie<FullKey, Payload, PayloadTraits> &b);
+ operator== <> (const trie<FullKey, Payload, PayloadTraits, PolicyHook> &a,
+ const trie<FullKey, Payload, PayloadTraits, PolicyHook> &b);
friend std::size_t
- hash_value <> (const trie<FullKey, Payload, PayloadTraits> &trie_node);
+ hash_value <> (const trie<FullKey, Payload, PayloadTraits, PolicyHook> &trie_node);
inline std::pair<iterator, bool>
- insert (const FullKey &key, typename PayloadTraits::const_pointer_type payload);
+ insert (const FullKey &key,
+ typename PayloadTraits::const_pointer_type payload);
/**
* @brief Removes payload (if it exists) and if there are no children, prunes parents trie
@@ -151,9 +162,21 @@
{
return 0;
}
+
+ typename PayloadTraits::const_pointer_type
+ payload () const
+ {
+ return payload_;
+ }
+
+ void
+ set_payload (typename PayloadTraits::const_pointer_type payload)
+ {
+ payload_ = payload;
+ }
- // inline const_iterator
- // find () const;
+ inline void
+ PrintStat (std::ostream &os) const;
private:
//The disposer object function
@@ -164,20 +187,32 @@
// std::cout << "Deleting " << delete_this << "\n";
delete delete_this;
}
- };
+ };
+
+ template<class D>
+ struct array_disposer
+ {
+ void operator() (D *array)
+ {
+ delete [] array;
+ }
+ };
friend
std::ostream&
operator<< < > (std::ostream &os, const trie &trie_node);
-
+
+public:
+ PolicyHook policy_hook_;
+
private:
- bi::unordered_set_member_hook<> member_hook_;
+ bi::unordered_set_member_hook<> unordered_set_member_hook_;
// necessary typedefs
typedef trie self_type;
typedef bi::member_hook< trie,
- bi::unordered_set_member_hook< >, &trie::member_hook_ > member_hook;
- typedef bi::unordered_set< trie, member_hook > unordered_set;
+ bi::unordered_set_member_hook< >, &trie::unordered_set_member_hook_ > member_hook;
+ typedef bi::unordered_set< trie, member_hook > unordered_set;
typedef typename unordered_set::bucket_type bucket_type;
typedef typename unordered_set::bucket_traits bucket_traits;
@@ -191,37 +226,41 @@
size_t bucketIncrement_;
size_t bucketSize_;
- bucket_type *buckets_;
+ typedef boost::interprocess::unique_ptr< bucket_type, array_disposer<bucket_type> > buckets_array;
+ buckets_array buckets_;
unordered_set children_;
typename PayloadTraits::const_pointer_type payload_;
trie *parent_; // to make cleaning effective
};
-template<typename FullKey, typename Payload, typename PayloadTraits>
-trie<FullKey, Payload, PayloadTraits>::trie (const trie::Key &key, size_t bucketSize, size_t bucketIncrement)
+template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook>
+trie<FullKey, Payload, PayloadTraits, PolicyHook>
+::trie (const trie::Key &key, size_t bucketSize, size_t bucketIncrement)
: key_ (key)
, initialBucketSize_ (bucketSize)
, bucketIncrement_ (bucketIncrement)
, bucketSize_ (initialBucketSize_)
- , buckets_ (new bucket_type [bucketSize_])
- , children_ (bucket_traits (buckets_, bucketSize_))
+ , buckets_ (new bucket_type [bucketSize_]) //cannot use normal pointer, because lifetime of buckets should be larger than lifetime of the container
+ , children_ (bucket_traits (buckets_.get (), bucketSize_))
, payload_ (PayloadTraits::empty_payload)
, parent_ (0)
{
}
-template<typename FullKey, typename Payload, typename PayloadTraits>
-trie<FullKey, Payload, PayloadTraits>::~trie ()
+template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook>
+trie<FullKey, Payload, PayloadTraits, PolicyHook>
+::~trie ()
{
+ payload_ = PayloadTraits::empty_payload; // necessary for smart pointers...
children_.clear_and_dispose (trie_delete_disposer ());
- delete [] buckets_;
}
-template<typename FullKey, typename Payload, typename PayloadTraits>
+template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook>
inline
-std::pair<typename trie<FullKey, Payload, PayloadTraits>::iterator, bool>
-trie<FullKey, Payload, PayloadTraits>::insert (const FullKey &key, typename PayloadTraits::const_pointer_type payload)
+std::pair<typename trie<FullKey, Payload, PayloadTraits, PolicyHook>::iterator, bool>
+trie<FullKey, Payload, PayloadTraits, PolicyHook>
+::insert (const FullKey &key, typename PayloadTraits::const_pointer_type payload)
{
trie *trieNode = this;
@@ -234,13 +273,12 @@
// std::cout << "new " << newNode << "\n";
newNode->parent_ = trieNode;
- if (trieNode->children_.size () > trieNode->bucketSize_)
+ if (trieNode->children_.size () >= trieNode->bucketSize_)
{
trieNode->bucketSize_ += trieNode->bucketIncrement_;
- bucket_type *newBuckets = new bucket_type [trieNode->bucketSize_];
- trieNode->children_.rehash (bucket_traits (newBuckets, trieNode->bucketSize_));
- delete [] trieNode->buckets_;
- trieNode->buckets_ = newBuckets;
+ buckets_array newBuckets (new bucket_type [trieNode->bucketSize_]);
+ trieNode->children_.rehash (bucket_traits (newBuckets.get (), trieNode->bucketSize_));
+ trieNode->buckets_.swap (newBuckets);
}
std::pair< typename unordered_set::iterator, bool > ret =
@@ -261,12 +299,13 @@
return std::make_pair (trieNode, false);
}
-template<typename FullKey, typename Payload, typename PayloadTraits>
+template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook>
inline
-boost::tuple<typename trie<FullKey, Payload, PayloadTraits>::iterator,
+boost::tuple<typename trie<FullKey, Payload, PayloadTraits, PolicyHook>::iterator,
bool,
- typename trie<FullKey, Payload, PayloadTraits>::iterator>
-trie<FullKey, Payload, PayloadTraits>::find (const FullKey &key)
+ typename trie<FullKey, Payload, PayloadTraits, PolicyHook>::iterator>
+trie<FullKey, Payload, PayloadTraits, PolicyHook>
+::find (const FullKey &key)
{
trie *trieNode = this;
iterator foundNode = (payload_ != PayloadTraits::empty_payload) ? this : 0;
@@ -292,9 +331,10 @@
return boost::make_tuple (foundNode, reachLast, trieNode);
}
-template<typename FullKey, typename Payload, typename PayloadTraits>
-inline typename trie<FullKey, Payload, PayloadTraits>::iterator
-trie<FullKey, Payload, PayloadTraits>::find ()
+template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook>
+inline typename trie<FullKey, Payload, PayloadTraits, PolicyHook>::iterator
+trie<FullKey, Payload, PayloadTraits, PolicyHook>
+::find ()
{
if (payload_ != PayloadTraits::empty_payload)
return this;
@@ -310,15 +350,16 @@
return 0;
}
-template<typename FullKey, typename Payload, typename PayloadTraits>
+template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook>
template<class Predicate>
-inline typename trie<FullKey, Payload, PayloadTraits>::iterator
-trie<FullKey, Payload, PayloadTraits>::find_if (Predicate pred)
+inline typename trie<FullKey, Payload, PayloadTraits, PolicyHook>::iterator
+trie<FullKey, Payload, PayloadTraits, PolicyHook>
+::find_if (Predicate pred)
{
if (payload_ != PayloadTraits::empty_payload && pred (payload_))
return this;
- typedef trie<FullKey, Payload, PayloadTraits> trie;
+ typedef trie<FullKey, Payload, PayloadTraits, PolicyHook> trie;
BOOST_FOREACH (const trie &subnode, children_)
{
iterator value = subnode.find ();
@@ -330,17 +371,17 @@
}
-template<typename FullKey, typename Payload, typename PayloadTraits>
+template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook>
inline void
-trie<FullKey, Payload, PayloadTraits>::erase ()
+trie<FullKey, Payload, PayloadTraits, PolicyHook>::erase ()
{
payload_ = PayloadTraits::empty_payload;
prune ();
}
-template<typename FullKey, typename Payload, typename PayloadTraits>
+template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook>
inline void
-trie<FullKey, Payload, PayloadTraits>::prune ()
+trie<FullKey, Payload, PayloadTraits, PolicyHook>::prune ()
{
if (payload_ == 0 && children_.size () == 0)
{
@@ -353,12 +394,12 @@
}
}
-template<typename FullKey, typename Payload, typename PayloadTraits>
+template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook>
inline std::ostream&
-operator << (std::ostream &os, const trie<FullKey, Payload, PayloadTraits> &trie_node)
+operator << (std::ostream &os, const trie<FullKey, Payload, PayloadTraits, PolicyHook> &trie_node)
{
os << "# " << trie_node.key_ << ((trie_node.payload_ != 0)?"*":"") << std::endl;
- typedef trie<FullKey, Payload, PayloadTraits> trie;
+ typedef trie<FullKey, Payload, PayloadTraits, PolicyHook> trie;
BOOST_FOREACH (const trie &subnode, trie_node.children_)
{
os << "\"" << &trie_node << "\"" << " [label=\"" << trie_node.key_ << ((trie_node.payload_ != 0)?"*":"") << "\"]\n";
@@ -371,16 +412,204 @@
return os;
}
-template<typename FullKey, typename Payload, typename PayloadTraits>
+template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook>
+inline void
+trie<FullKey, Payload, PayloadTraits, PolicyHook>::PrintStat (std::ostream &os) const
+{
+ os << "# " << key_ << ((payload_ != 0)?"*":"") << ": " << children_.size() << " children" << std::endl;
+ for (size_t bucket = 0, maxbucket = children_.bucket_count ();
+ bucket < maxbucket;
+ bucket++)
+ {
+ os << " " << children_.bucket_size (bucket);
+ }
+ os << "\n";
+
+ typedef trie<FullKey, Payload, PayloadTraits, PolicyHook> trie;
+ BOOST_FOREACH (const trie &subnode, children_)
+ {
+ subnode.PrintStat (os);
+ }
+}
+
+
+template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook>
inline bool
-operator == (const trie<FullKey, Payload, PayloadTraits> &a, const trie<FullKey, Payload, PayloadTraits> &b)
+operator == (const trie<FullKey, Payload, PayloadTraits, PolicyHook> &a,
+ const trie<FullKey, Payload, PayloadTraits, PolicyHook> &b)
{
return a.key_ == b.key_;
}
-template<typename FullKey, typename Payload, typename PayloadTraits>
+template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook>
inline std::size_t
-hash_value (const trie<FullKey, Payload, PayloadTraits> &trie_node)
+hash_value (const trie<FullKey, Payload, PayloadTraits, PolicyHook> &trie_node)
{
return boost::hash_value (trie_node.key_);
}
+
+
+
+template<typename FullKey,
+ typename Payload, typename PayloadTraits
+ >
+struct lru_policy_traits
+{
+ typedef trie< FullKey, Payload, PayloadTraits, bi::list_member_hook<> > parent_trie;
+ typedef typename bi::list< parent_trie,
+ bi::member_hook< parent_trie,
+ bi::list_member_hook<>,
+ &parent_trie::policy_hook_ > > policy_container;
+
+ class policy : public policy_container
+ {
+ public:
+ policy ()
+ : max_size_ (100)
+ {
+ }
+
+ inline void
+ update (typename parent_trie::iterator item)
+ {
+ // do relocation
+ policy_container::splice (policy_container::end (),
+ *this,
+ policy_container::s_iterator_to (*item));
+ }
+
+ inline void
+ insert (typename parent_trie::iterator item)
+ {
+ if (policy_container::size () >= max_size_)
+ {
+ typename parent_trie::iterator oldItem = &(*policy_container::begin ());
+ policy_container::pop_front ();
+ oldItem->erase ();
+ }
+
+ policy_container::push_back (*item);
+ }
+
+ inline void
+ lookup (typename parent_trie::iterator item)
+ {
+ // do relocation
+ policy_container::splice (policy_container::end (),
+ *this,
+ policy_container::s_iterator_to (*item));
+ }
+
+ inline void
+ erase (typename parent_trie::iterator item)
+ {
+ policy_container::erase (policy_container::s_iterator_to (*item));
+ }
+
+ inline void
+ set_max_size (size_t max_size)
+ {
+ max_size_ = max_size;
+ }
+
+ private:
+ size_t max_size_;
+ };
+};
+
+
+
+template<typename FullKey,
+ typename Payload, typename PayloadTraits = pointer_payload_traits<Payload>,
+ typename policy_traits = lru_policy_traits<FullKey, Payload, PayloadTraits>
+ >
+class indexed_trie
+{
+public:
+ typedef trie< FullKey, Payload, PayloadTraits > parent_trie;
+ typedef typename parent_trie::iterator iterator;
+
+ inline
+ indexed_trie (size_t bucketSize = 10, size_t bucketIncrement = 10)
+ : trie_ ("", bucketSize, bucketIncrement)
+ {
+ }
+
+ inline std::pair< iterator, bool >
+ insert (const FullKey &key, typename PayloadTraits::const_pointer_type payload)
+ {
+ std::pair<iterator, bool> item =
+ trie_.insert (key, payload);
+
+ if (item.second) // real insert
+ {
+ policy_.insert (s_iterator_to (item.first));
+ }
+ else
+ {
+ item.first->set_payload (payload);
+ // policy_traits::update (*item.first);
+ }
+
+ return item;
+ }
+
+ inline void
+ erase (iterator node)
+ {
+ if (node == end ()) return;
+
+ policy_.erase (s_iterator_to (node));
+ node->erase (); // will do cleanup here
+ }
+
+ /**
+ * @brief Perform the longest prefix match
+ * @param key the key for which to perform the longest prefix match
+ *
+ * For subsequent direct searches, policy_.lookup () should be called manually
+ *
+ * @return ->second is true if prefix in ->first is longer than key
+ * ->third is always last node searched
+ */
+ inline boost::tuple< iterator, bool, iterator >
+ find (const FullKey &key)
+ {
+ boost::tuple< iterator, bool, iterator > item = trie_.find (key);
+ if (item.template get<0> () != trie_.end ())
+ {
+ policy_.lookup (s_iterator_to (item.template get<0> ()));
+ }
+ return boost::make_tuple (s_iterator_to (item.template get<0> ()),
+ item.template get<1> (),
+ s_iterator_to (item.template get<2> ()));
+ }
+
+ iterator end ()
+ {
+ return 0;
+ }
+
+ const parent_trie &
+ getTrie () const { return trie_; }
+
+ const typename policy_traits::policy &
+ getPolicy () const { return policy_; }
+
+ typename policy_traits::policy &
+ getPolicy () { return policy_; }
+
+ static inline iterator
+ s_iterator_to (typename parent_trie::iterator item)
+ {
+ if (item == 0)
+ return 0;
+ else
+ return &(*item);
+ }
+
+private:
+ parent_trie trie_;
+ typename policy_traits::policy policy_;
+};
+