forked from cawka/ndn.cxx
diff --git a/ndn-cpp/trie/detail/functor-hook.h b/ndn-cpp/trie/detail/functor-hook.h
new file mode 100644
index 0000000..f34969c
--- /dev/null
+++ b/ndn-cpp/trie/detail/functor-hook.h
@@ -0,0 +1,70 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef FUNCTOR_HOOK_H_
+#define FUNCTOR_HOOK_H_
+
+#include <boost/intrusive/parent_from_member.hpp>
+
+namespace ns3 {
+namespace ndn {
+namespace ndnSIM {
+namespace detail {
+
+template<class BaseHook, class ValueType, int N>
+struct FunctorHook
+{
+ typedef typename BaseHook::template index<N>::type hook_type;
+ typedef hook_type* hook_ptr;
+ typedef const hook_type* const_hook_ptr;
+
+ typedef ValueType value_type;
+ typedef value_type* pointer;
+ typedef const value_type* const_pointer;
+
+ //Required static functions
+ static hook_ptr to_hook_ptr (value_type &value)
+ { return &value.policy_hook_.template get<N> (); }
+
+ static const_hook_ptr to_hook_ptr(const value_type &value)
+ { return &value.policy_hook_.template get<N> (); }
+
+ static pointer to_value_ptr(hook_ptr n)
+ {
+ return
+ boost::intrusive::get_parent_from_member<value_type>
+ (static_cast<BaseHook*> (boost::intrusive::get_parent_from_member< wrap<hook_type> >(n, &wrap<hook_type>::value_)),
+ &value_type::policy_hook_);
+ }
+ static const_pointer to_value_ptr(const_hook_ptr n)
+ {
+ return
+ boost::intrusive::get_parent_from_member<value_type>
+ (static_cast<const BaseHook*> (boost::intrusive::get_parent_from_member< wrap<hook_type> >(n, &wrap<hook_type>::value_)),
+ &value_type::policy_hook_);
+ }
+};
+
+} // detail
+} // ndnSIM
+} // ndn
+} // ns3
+
+#endif // FUNCTOR_HOOK_H_
diff --git a/ndn-cpp/trie/detail/multi-policy-container.h b/ndn-cpp/trie/detail/multi-policy-container.h
new file mode 100644
index 0000000..c1251e9
--- /dev/null
+++ b/ndn-cpp/trie/detail/multi-policy-container.h
@@ -0,0 +1,175 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2011 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef MULTI_POLICY_CONTAINER_H_
+#define MULTI_POLICY_CONTAINER_H_
+
+#include <boost/mpl/inherit_linearly.hpp>
+#include <boost/mpl/at.hpp>
+
+namespace ns3 {
+namespace ndn {
+namespace ndnSIM {
+namespace detail {
+
+template< class Base, class Value >
+struct policy_wrap
+{
+ policy_wrap (Base &base) : value_ (base) { }
+ Value value_;
+};
+
+template< class Base, class Super/*empy_wrap/previous level*/, class Value/*policy_wrap< element in vector >*/ >
+struct inherit_with_base : Super, Value
+{
+ inherit_with_base (Base &base) : Super (base), Value (base) { }
+
+ void
+ update (typename Base::iterator item)
+ {
+ Value::value_.update (item);
+ Super::update (item);
+ }
+
+ bool
+ insert (typename Base::iterator item)
+ {
+ bool ok = Value::value_.insert (item);
+ if (!ok)
+ return false;
+
+ ok = Super::insert (item);
+ if (!ok)
+ {
+ Value::value_.erase (item);
+ return false;
+ }
+ return true;
+ }
+
+ void
+ lookup (typename Base::iterator item)
+ {
+ Value::value_.lookup (item);
+ Super::lookup (item);
+ }
+
+ void
+ erase (typename Base::iterator item)
+ {
+ Value::value_.erase (item);
+ Super::erase (item);
+ }
+
+ void
+ clear ()
+ {
+ Value::value_.clear ();
+ Super::clear ();
+ }
+};
+
+template< class Base >
+struct empty_policy_wrap
+{
+ empty_policy_wrap (Base &base) { }
+
+ void update (typename Base::iterator item) {}
+ bool insert (typename Base::iterator item) { return true; }
+ void lookup (typename Base::iterator item) {}
+ void erase (typename Base::iterator item) {}
+ void clear () {}
+};
+
+template< class Base, class Vector >
+struct multi_policy_container
+ : public boost::mpl::fold< Vector,
+ empty_policy_wrap<Base>,
+ inherit_with_base<Base,
+ boost::mpl::_1/*empty/previous*/,
+ policy_wrap<Base, boost::mpl::_2>/*element in vector*/>
+ >::type
+{
+ typedef typename boost::mpl::fold< Vector,
+ empty_policy_wrap<Base>,
+ inherit_with_base<Base,
+ boost::mpl::_1/*empty/previous*/,
+ policy_wrap<Base, boost::mpl::_2>/*element in vector*/>
+ >::type super;
+
+ typedef typename boost::mpl::at_c<Vector, 0>::type::iterator iterator;
+ typedef typename boost::mpl::at_c<Vector, 0>::type::const_iterator const_iterator;
+
+ iterator begin () { return this->get<0> ().begin (); }
+ const_iterator begin () const { return this->get<0> ().begin (); }
+
+ iterator end () { return this->get<0> ().end (); }
+ const_iterator end () const { return this->get<0> ().end (); }
+
+ size_t size () const { return this->get<0> ().size (); }
+
+ multi_policy_container (Base &base)
+ : super (base)
+ { }
+
+ template<int N>
+ struct index
+ {
+ typedef typename boost::mpl::at_c<Vector, N>::type type;
+ };
+
+ template<class T>
+ T &
+ get ()
+ {
+ return static_cast< policy_wrap<Base, T> &> (*this).value_;
+ }
+
+ template<class T>
+ const T &
+ get () const
+ {
+ return static_cast< const policy_wrap<Base, T> &> (*this).value_;
+ }
+
+ template<int N>
+ typename boost::mpl::at_c<Vector, N>::type &
+ get ()
+ {
+ typedef typename boost::mpl::at_c<Vector, N>::type T;
+ return static_cast< policy_wrap<Base, T> &> (*this).value_;
+ }
+
+ template<int N>
+ const typename boost::mpl::at_c<Vector, N>::type &
+ get () const
+ {
+ typedef typename boost::mpl::at_c<Vector, N>::type T;
+ return static_cast< const policy_wrap<Base, T> &> (*this).value_;
+ }
+};
+
+
+} // detail
+} // ndnSIM
+} // ndn
+} // ns3
+
+#endif // MULTI_POLICY_CONTAINER_H_
diff --git a/ndn-cpp/trie/detail/multi-type-container.h b/ndn-cpp/trie/detail/multi-type-container.h
new file mode 100644
index 0000000..d4971c4
--- /dev/null
+++ b/ndn-cpp/trie/detail/multi-type-container.h
@@ -0,0 +1,86 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2011 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef MULTI_TYPE_CONTAINER_H_
+#define MULTI_TYPE_CONTAINER_H_
+
+#include <boost/mpl/inherit_linearly.hpp>
+#include <boost/mpl/inherit.hpp>
+#include <boost/mpl/at.hpp>
+
+namespace ns3 {
+namespace ndn {
+namespace ndnSIM {
+namespace detail {
+
+template <class T>
+struct wrap
+{
+ T value_;
+};
+
+template< class Vector >
+struct multi_type_container
+ : public boost::mpl::inherit_linearly< Vector, boost::mpl::inherit<wrap<boost::mpl::_2>, boost::mpl::_1 >
+ >::type
+{
+ template<int N>
+ struct index
+ {
+ typedef typename boost::mpl::at_c<Vector, N>::type type;
+ };
+
+ template<class T>
+ T &
+ get ()
+ {
+ return static_cast< wrap<T> &> (*this).value_;
+ }
+
+ template<class T>
+ const T &
+ get () const
+ {
+ return static_cast< const wrap<T> &> (*this).value_;
+ }
+
+ template<int N>
+ typename boost::mpl::at_c<Vector, N>::type &
+ get ()
+ {
+ typedef typename boost::mpl::at_c<Vector, N>::type T;
+ return static_cast< wrap<T> &> (*this).value_;
+ }
+
+ template<int N>
+ const typename boost::mpl::at_c<Vector, N>::type &
+ get () const
+ {
+ typedef typename boost::mpl::at_c<Vector, N>::type T;
+ return static_cast< const wrap<T> &> (*this).value_;
+ }
+};
+
+} // detail
+} // ndnSIM
+} // ndn
+} // ns3
+
+#endif // MULTI_TYPE_CONTAINER_H_
diff --git a/ndn-cpp/trie/payload-traits/pointer.h b/ndn-cpp/trie/payload-traits/pointer.h
new file mode 100644
index 0000000..8290fbe
--- /dev/null
+++ b/ndn-cpp/trie/payload-traits/pointer.h
@@ -0,0 +1,40 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2013, Regents of the University of California
+ * Alexander Afanasyev
+ *
+ * BSD license, See the LICENSE file for more information
+ *
+ * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef NDN_TRIE_PAYLOAD_TRAITS_POINTER_H
+#define NDN_TRIE_PAYLOAD_TRAITS_POINTER_H
+
+namespace ndn {
+namespace trie {
+
+template<typename Payload, typename BasePayload = Payload>
+struct pointer_payload_traits
+{
+ typedef Payload payload_type; // general type of the payload
+ typedef Payload* storage_type; // how the payload is actually stored
+ typedef Payload* insert_type; // what parameter is inserted
+
+ typedef Payload* return_type; // what is returned on access
+ typedef const Payload* const_return_type; // what is returned on const access
+
+ typedef BasePayload* base_type; // base type of the entry (when implementation details need to be hidden)
+ typedef const BasePayload* const_base_type; // const base type of the entry (when implementation details need to be hidden)
+
+ static Payload* empty_payload;
+};
+
+template<typename Payload, typename BasePayload>
+Payload*
+pointer_payload_traits<Payload, BasePayload>::empty_payload = NULL;
+
+} // trie
+} // ndn
+
+#endif // NDN_TRIE_PAYLOAD_TRAITS_POINTER_H
diff --git a/ndn-cpp/trie/payload-traits/ptr.h b/ndn-cpp/trie/payload-traits/ptr.h
new file mode 100644
index 0000000..3caf020
--- /dev/null
+++ b/ndn-cpp/trie/payload-traits/ptr.h
@@ -0,0 +1,40 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2013, Regents of the University of California
+ * Alexander Afanasyev
+ *
+ * BSD license, See the LICENSE file for more information
+ *
+ * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef NDN_TRIE_PAYLOAD_TRAITS_PTR_H
+#define NDN_TRIE_PAYLOAD_TRAITS_PTR_H
+
+namespace ndn {
+namespace trie {
+
+template<typename Payload, typename BasePayload = Payload>
+struct ptr_payload_traits
+{
+ typedef Payload payload_type;
+ typedef Ptr<Payload> storage_type;
+ typedef Ptr<Payload> insert_type;
+
+ typedef Ptr<Payload> return_type;
+ typedef Ptr<const Payload> const_return_type;
+
+ typedef Ptr<BasePayload> base_type;
+ typedef Ptr<const BasePayload> const_base_type;
+
+ static Ptr<Payload> empty_payload;
+};
+
+template<typename Payload, typename BasePayload>
+Ptr<Payload>
+ptr_payload_traits<Payload, BasePayload>::empty_payload; // = Ptr<Payload> ();
+
+} // trie
+} // ndn
+
+#endif // NDN_TRIE_PAYLOAD_TRAITS_PTR_H
diff --git a/ndn-cpp/trie/policies/counting-policy.h b/ndn-cpp/trie/policies/counting-policy.h
new file mode 100644
index 0000000..d27f915
--- /dev/null
+++ b/ndn-cpp/trie/policies/counting-policy.h
@@ -0,0 +1,101 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2013, Regents of the University of California
+ * Alexander Afanasyev
+ *
+ * BSD license, See the LICENSE file for more information
+ *
+ * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef COUNTING_POLICY_H_
+#define COUNTING_POLICY_H_
+
+#include <boost/intrusive/options.hpp>
+#include <boost/intrusive/list.hpp>
+
+namespace ndn {
+namespace trie {
+
+/**
+ * @brief Traits for policy that just keeps track of number of elements
+ * It's doing a rather expensive job, but just in case it needs to be extended later
+ */
+struct counting_policy_traits
+{
+ /// @brief Name that can be used to identify the policy (e.g., for logging)
+ static std::string GetName () { return "Counting"; }
+
+ struct policy_hook_type : public boost::intrusive::list_member_hook<> {};
+
+ template<class Container>
+ struct container_hook
+ {
+ // could be class/struct implementation
+ typedef boost::intrusive::member_hook< Container,
+ policy_hook_type,
+ &Container::policy_hook_ > type;
+ };
+
+ template<class Base,
+ class Container,
+ class Hook>
+ struct policy
+ {
+ typedef typename boost::intrusive::list< Container, Hook > policy_container;
+
+ // could be just typedef
+ class type : public policy_container
+ {
+ public:
+ typedef Container parent_trie;
+
+ type (Base &base)
+ : base_ (base)
+ {
+ }
+
+ inline void
+ update (typename parent_trie::iterator item)
+ {
+ // do nothing
+ }
+
+ inline bool
+ insert (typename parent_trie::iterator item)
+ {
+ policy_container::push_back (*item);
+ return true;
+ }
+
+ inline void
+ lookup (typename parent_trie::iterator item)
+ {
+ // do nothing
+ }
+
+ inline void
+ erase (typename parent_trie::iterator item)
+ {
+ policy_container::erase (policy_container::s_iterator_to (*item));
+ }
+
+ inline void
+ clear ()
+ {
+ policy_container::clear ();
+ }
+
+ private:
+ type () : base_(*((Base*)0)) { };
+
+ private:
+ Base &base_;
+ };
+ };
+};
+
+} // trie
+} // ndn
+
+#endif // COUNTING_POLICY_H_
diff --git a/ndn-cpp/trie/policies/empty-policy.h b/ndn-cpp/trie/policies/empty-policy.h
new file mode 100644
index 0000000..0cfe962
--- /dev/null
+++ b/ndn-cpp/trie/policies/empty-policy.h
@@ -0,0 +1,50 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2013, Regents of the University of California
+ * Alexander Afanasyev
+ *
+ * BSD license, See the LICENSE file for more information
+ *
+ * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef EMPTY_POLICY_H_
+#define EMPTY_POLICY_H_
+
+namespace ndn {
+namespace trie {
+
+/**
+ * @brief Traits for empty (bogus) replacement policy
+ */
+struct empty_policy_traits
+{
+ /// @brief Name that can be used to identify the policy (e.g., for logging)
+ static std::string GetName () { return ""; }
+
+ typedef void* policy_hook_type;
+
+ template<class Container> struct container_hook { typedef void* type; };
+
+ template<class Base,
+ class Container,
+ class Hook>
+ struct policy
+ {
+ struct type
+ {
+ inline type (Base &base) {}
+
+ inline void update (typename Container::iterator) { }
+ inline bool insert (typename Container::iterator) { return true; }
+ inline void lookup (typename Container::iterator item) { }
+ inline void erase (typename Container::iterator item) { }
+ inline void clear () { }
+ };
+ };
+};
+
+} // trie
+} // ndn
+
+#endif // EMPTY_POLICY_H_
diff --git a/ndn-cpp/trie/policies/fifo-policy.h b/ndn-cpp/trie/policies/fifo-policy.h
new file mode 100644
index 0000000..7acad2b
--- /dev/null
+++ b/ndn-cpp/trie/policies/fifo-policy.h
@@ -0,0 +1,119 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2013, Regents of the University of California
+ * Alexander Afanasyev
+ *
+ * BSD license, See the LICENSE file for more information
+ *
+ * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef FIFO_POLICY_H_
+#define FIFO_POLICY_H_
+
+#include <boost/intrusive/options.hpp>
+#include <boost/intrusive/list.hpp>
+
+namespace ndn {
+namespace trie {
+
+/**
+ * @brief Traits for First In First Out replacement policy
+ */
+struct fifo_policy_traits
+{
+ /// @brief Name that can be used to identify the policy (e.g., for logging)
+ static std::string GetName () { return "Fifo"; }
+
+ struct policy_hook_type : public boost::intrusive::list_member_hook<> {};
+
+ template<class Container>
+ struct container_hook
+ {
+ // could be class/struct implementation
+ typedef boost::intrusive::member_hook< Container,
+ policy_hook_type,
+ &Container::policy_hook_ > type;
+ };
+
+ template<class Base,
+ class Container,
+ class Hook>
+ struct policy
+ {
+ typedef typename boost::intrusive::list< Container, Hook > policy_container;
+
+ // could be just typedef
+ class type : public policy_container
+ {
+ public:
+ typedef Container parent_trie;
+
+ type (Base &base)
+ : base_ (base)
+ , max_size_ (100)
+ {
+ }
+
+ inline void
+ update (typename parent_trie::iterator item)
+ {
+ // do nothing
+ }
+
+ inline bool
+ insert (typename parent_trie::iterator item)
+ {
+ if (max_size_ != 0 && policy_container::size () >= max_size_)
+ {
+ base_.erase (&(*policy_container::begin ()));
+ }
+
+ policy_container::push_back (*item);
+ return true;
+ }
+
+ inline void
+ lookup (typename parent_trie::iterator item)
+ {
+ // do nothing
+ }
+
+ inline void
+ erase (typename parent_trie::iterator item)
+ {
+ policy_container::erase (policy_container::s_iterator_to (*item));
+ }
+
+ inline void
+ clear ()
+ {
+ policy_container::clear ();
+ }
+
+ inline void
+ set_max_size (size_t max_size)
+ {
+ max_size_ = max_size;
+ }
+
+ inline size_t
+ get_max_size () const
+ {
+ return max_size_;
+ }
+
+ private:
+ type () : base_(*((Base*)0)) { };
+
+ private:
+ Base &base_;
+ size_t max_size_;
+ };
+ };
+};
+
+} // trie
+} // ndn
+
+#endif
diff --git a/ndn-cpp/trie/policies/lfu-policy.h b/ndn-cpp/trie/policies/lfu-policy.h
new file mode 100644
index 0000000..802f64b
--- /dev/null
+++ b/ndn-cpp/trie/policies/lfu-policy.h
@@ -0,0 +1,149 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2013, Regents of the University of California
+ * Alexander Afanasyev
+ *
+ * BSD license, See the LICENSE file for more information
+ *
+ * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef LFU_POLICY_H_
+#define LFU_POLICY_H_
+
+#include <boost/intrusive/options.hpp>
+#include <boost/intrusive/set.hpp>
+
+namespace ndn {
+namespace trie {
+
+/**
+ * @brief Traits for LFU replacement policy
+ */
+struct lfu_policy_traits
+{
+ /// @brief Name that can be used to identify the policy (e.g., for logging)
+ static std::string GetName () { return "Lfu"; }
+
+ struct policy_hook_type : public boost::intrusive::set_member_hook<> { double frequency; };
+
+ template<class Container>
+ struct container_hook
+ {
+ typedef boost::intrusive::member_hook< Container,
+ policy_hook_type,
+ &Container::policy_hook_ > type;
+ };
+
+ template<class Base,
+ class Container,
+ class Hook>
+ struct policy
+ {
+ static double& get_order (typename Container::iterator item)
+ {
+ return static_cast<policy_hook_type*>
+ (policy_container::value_traits::to_node_ptr(*item))->frequency;
+ }
+
+ static const double& get_order (typename Container::const_iterator item)
+ {
+ return static_cast<const policy_hook_type*>
+ (policy_container::value_traits::to_node_ptr(*item))->frequency;
+ }
+
+ template<class Key>
+ struct MemberHookLess
+ {
+ bool operator () (const Key &a, const Key &b) const
+ {
+ return get_order (&a) < get_order (&b);
+ }
+ };
+
+ typedef boost::intrusive::multiset< Container,
+ boost::intrusive::compare< MemberHookLess< Container > >,
+ Hook > policy_container;
+
+ // could be just typedef
+ class type : public policy_container
+ {
+ public:
+ typedef policy policy_base; // to get access to get_order methods from outside
+ typedef Container parent_trie;
+
+ type (Base &base)
+ : base_ (base)
+ , max_size_ (100)
+ {
+ }
+
+ inline void
+ update (typename parent_trie::iterator item)
+ {
+ policy_container::erase (policy_container::s_iterator_to (*item));
+ get_order (item) += 1;
+ policy_container::insert (*item);
+ }
+
+ inline bool
+ insert (typename parent_trie::iterator item)
+ {
+ get_order (item) = 0;
+
+ if (max_size_ != 0 && policy_container::size () >= max_size_)
+ {
+ // this erases the "least frequently used item" from cache
+ base_.erase (&(*policy_container::begin ()));
+ }
+
+ policy_container::insert (*item);
+ return true;
+ }
+
+ inline void
+ lookup (typename parent_trie::iterator item)
+ {
+ policy_container::erase (policy_container::s_iterator_to (*item));
+ get_order (item) += 1;
+ policy_container::insert (*item);
+ }
+
+ inline void
+ erase (typename parent_trie::iterator item)
+ {
+ policy_container::erase (policy_container::s_iterator_to (*item));
+ }
+
+ inline void
+ clear ()
+ {
+ policy_container::clear ();
+ }
+
+ inline void
+ set_max_size (size_t max_size)
+ {
+ max_size_ = max_size;
+ }
+
+ inline size_t
+ get_max_size () const
+ {
+ return max_size_;
+ }
+
+ private:
+ type () : base_(*((Base*)0)) { };
+
+ private:
+ Base &base_;
+ size_t max_size_;
+ };
+ };
+};
+
+} // trie
+} // ndn
+
+#endif // LFU_POLICY_H
diff --git a/ndn-cpp/trie/policies/lru-policy.h b/ndn-cpp/trie/policies/lru-policy.h
new file mode 100644
index 0000000..ad3a382
--- /dev/null
+++ b/ndn-cpp/trie/policies/lru-policy.h
@@ -0,0 +1,124 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2013, Regents of the University of California
+ * Alexander Afanasyev
+ *
+ * BSD license, See the LICENSE file for more information
+ *
+ * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef LRU_POLICY_H_
+#define LRU_POLICY_H_
+
+#include <boost/intrusive/options.hpp>
+#include <boost/intrusive/list.hpp>
+
+namespace ndn {
+namespace trie {
+
+/**
+ * @brief Traits for Least Recently Used replacement policy
+ */
+struct lru_policy_traits
+{
+ /// @brief Name that can be used to identify the policy (e.g., for logging)
+ static std::string GetName () { return "Lru"; }
+
+ struct policy_hook_type : public boost::intrusive::list_member_hook<> {};
+
+ template<class Container>
+ struct container_hook
+ {
+ typedef boost::intrusive::member_hook< Container,
+ policy_hook_type,
+ &Container::policy_hook_ > type;
+ };
+
+ template<class Base,
+ class Container,
+ class Hook>
+ struct policy
+ {
+ typedef typename boost::intrusive::list< Container, Hook > policy_container;
+
+ // could be just typedef
+ class type : public policy_container
+ {
+ public:
+ typedef Container parent_trie;
+
+ type (Base &base)
+ : base_ (base)
+ , 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 bool
+ insert (typename parent_trie::iterator item)
+ {
+ if (max_size_ != 0 && policy_container::size () >= max_size_)
+ {
+ base_.erase (&(*policy_container::begin ()));
+ }
+
+ policy_container::push_back (*item);
+ return true;
+ }
+
+ 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
+ clear ()
+ {
+ policy_container::clear ();
+ }
+
+ inline void
+ set_max_size (size_t max_size)
+ {
+ max_size_ = max_size;
+ }
+
+ inline size_t
+ get_max_size () const
+ {
+ return max_size_;
+ }
+
+ private:
+ type () : base_(*((Base*)0)) { };
+
+ private:
+ Base &base_;
+ size_t max_size_;
+ };
+ };
+};
+
+} // trie
+} // ndn
+
+#endif
diff --git a/ndn-cpp/trie/policies/multi-policy.h b/ndn-cpp/trie/policies/multi-policy.h
new file mode 100644
index 0000000..739de7b
--- /dev/null
+++ b/ndn-cpp/trie/policies/multi-policy.h
@@ -0,0 +1,177 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2013, Regents of the University of California
+ * Alexander Afanasyev
+ *
+ * BSD license, See the LICENSE file for more information
+ *
+ * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef MULTI_POLICY_H_
+#define MULTI_POLICY_H_
+
+#include "detail/multi-type-container.h"
+#include "detail/multi-policy-container.h"
+#include "detail/functor-hook.h"
+
+#include <boost/mpl/size.hpp>
+#include <boost/mpl/at.hpp>
+#include <boost/mpl/range_c.hpp>
+#include <boost/mpl/transform.hpp>
+#include <boost/mpl/back_inserter.hpp>
+#include <boost/mpl/vector.hpp>
+#include <boost/mpl/for_each.hpp>
+
+#include <boost/intrusive/options.hpp>
+
+namespace ndn {
+namespace trie {
+
+template<typename Policies> // e.g., mpl::vector1< lru_policy_traits >
+struct multi_policy_traits
+{
+ typedef Policies policy_traits;
+
+ struct getHook { template<class Item> struct apply { typedef typename Item::policy_hook_type type; }; };
+ typedef detail::multi_type_container< typename boost::mpl::transform1<policy_traits, getHook>::type > policy_hook_type;
+
+ template<class Container>
+ struct container_hook
+ {
+ typedef policy_hook_type type;
+ };
+
+ template<class Base,
+ class Container,
+ class Hook>
+ struct policy
+ {
+ typedef boost::mpl::range_c<int, 0, boost::mpl::size<policy_traits>::type::value> policies_range;
+
+ struct getPolicy
+ {
+ template<class Number>
+ struct apply
+ {
+ typedef
+ typename boost::mpl::at_c<policy_traits, Number::value>::type::
+ template policy<Base,
+ Container,
+ boost::intrusive::function_hook< detail::FunctorHook <Hook,
+ Container,
+ Number::value> > >::type
+ type;
+ };
+ };
+
+ typedef
+ typename boost::mpl::transform1<policies_range,
+ getPolicy,
+ boost::mpl::back_inserter< boost::mpl::vector0<> > >::type policies;
+
+
+ typedef detail::multi_policy_container< Base, policies > policy_container;
+
+ class type : public policy_container
+ {
+ public:
+ typedef policy policy_base; // to get access to get_time methods from outside
+ typedef Container parent_trie;
+
+ type (Base &base)
+ : policy_container (base)
+ {
+ }
+
+ inline void
+ update (typename parent_trie::iterator item)
+ {
+ policy_container::update (item);
+ }
+
+ inline bool
+ insert (typename parent_trie::iterator item)
+ {
+ return policy_container::insert (item);
+ }
+
+ inline void
+ lookup (typename parent_trie::iterator item)
+ {
+ policy_container::lookup (item);
+ }
+
+ inline void
+ erase (typename parent_trie::iterator item)
+ {
+ policy_container::erase (item);
+ }
+
+ inline void
+ clear ()
+ {
+ policy_container::clear ();
+ }
+
+ struct max_size_setter
+ {
+ max_size_setter (policy_container &container, size_t size) : m_container (container), m_size (size) { }
+
+ template< typename U > void operator() (U index)
+ {
+ m_container.template get<U::value> ().set_max_size (m_size);
+ }
+
+ private:
+ policy_container &m_container;
+ size_t m_size;
+ };
+
+ inline void
+ set_max_size (size_t max_size)
+ {
+ boost::mpl::for_each< boost::mpl::range_c<int, 0, boost::mpl::size<policy_traits>::type::value> >
+ (max_size_setter (*this, max_size));
+ }
+
+ inline size_t
+ get_max_size () const
+ {
+ // as max size should be the same everywhere, get the value from the first available policy
+ return policy_container::template get<0> ().get_max_size ();
+ }
+
+ };
+ };
+
+
+ struct name_getter
+ {
+ name_getter (std::string &name) : m_name (name) { }
+
+ template< typename U > void operator() (U index)
+ {
+ if (!m_name.empty ())
+ m_name += "::";
+ m_name += boost::mpl::at_c< policy_traits, U::value >::type::GetName ();
+ }
+
+ std::string &m_name;
+ };
+
+ /// @brief Name that can be used to identify the policy (e.g., for logging)
+ static std::string GetName ()
+ {
+ // combine names of all internal policies
+ std::string name;
+ boost::mpl::for_each< boost::mpl::range_c<int, 0, boost::mpl::size<policy_traits>::type::value> > (name_getter (name));
+
+ return name;
+ }
+};
+
+} // trie
+} // ndn
+
+#endif // MULTI_POLICY_H_
diff --git a/ndn-cpp/trie/policies/persistent-policy.h b/ndn-cpp/trie/policies/persistent-policy.h
new file mode 100644
index 0000000..d34f373
--- /dev/null
+++ b/ndn-cpp/trie/policies/persistent-policy.h
@@ -0,0 +1,119 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2013, Regents of the University of California
+ * Alexander Afanasyev
+ *
+ * BSD license, See the LICENSE file for more information
+ *
+ * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef PERSISTENT_POLICY_H_
+#define PERSISTENT_POLICY_H_
+
+#include <boost/intrusive/options.hpp>
+#include <boost/intrusive/list.hpp>
+
+namespace ndn {
+namespace trie {
+
+/**
+ * @brief Traits for persistent replacement policy
+ *
+ * In this policy entries are added until there is a space (controlled by set_max_size call).
+ * If maximum is reached, new entries will not be added and nothing will be removed from the container
+ */
+struct persistent_policy_traits
+{
+ /// @brief Name that can be used to identify the policy (e.g., for logging)
+ static std::string GetName () { return "Persistent"; }
+
+ struct policy_hook_type : public boost::intrusive::list_member_hook<> {};
+
+ template<class Container>
+ struct container_hook
+ {
+ typedef boost::intrusive::member_hook< Container,
+ policy_hook_type,
+ &Container::policy_hook_ > type;
+ };
+
+ template<class Base,
+ class Container,
+ class Hook>
+ struct policy
+ {
+ typedef typename boost::intrusive::list< Container, Hook > policy_container;
+
+ // could be just typedef
+ class type : public policy_container
+ {
+ public:
+ typedef Container parent_trie;
+
+ type (Base &base)
+ : base_ (base)
+ , max_size_ (100) // when 0, policy is not enforced
+ {
+ }
+
+ inline void
+ update (typename parent_trie::iterator item)
+ {
+ // do nothing
+ }
+
+ inline bool
+ insert (typename parent_trie::iterator item)
+ {
+ if (max_size_ != 0 && policy_container::size () >= max_size_)
+ return false;
+
+ policy_container::push_back (*item);
+ return true;
+ }
+
+ inline void
+ lookup (typename parent_trie::iterator item)
+ {
+ // do nothing
+ }
+
+ inline void
+ erase (typename parent_trie::iterator item)
+ {
+ policy_container::erase (policy_container::s_iterator_to (*item));
+ }
+
+ inline void
+ clear ()
+ {
+ policy_container::clear ();
+ }
+
+ inline void
+ set_max_size (size_t max_size)
+ {
+ max_size_ = max_size;
+ }
+
+ inline size_t
+ get_max_size () const
+ {
+ return max_size_;
+ }
+
+ private:
+ // type () : base_(*((Base*)0)) { };
+
+ private:
+ Base &base_;
+ size_t max_size_;
+ };
+ };
+};
+
+} // trie
+} // ndn
+
+#endif // PERSISTENT_POLICY_H_
diff --git a/ndn-cpp/trie/policies/random-policy.h b/ndn-cpp/trie/policies/random-policy.h
new file mode 100644
index 0000000..d896e89
--- /dev/null
+++ b/ndn-cpp/trie/policies/random-policy.h
@@ -0,0 +1,158 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2013, Regents of the University of California
+ * Alexander Afanasyev
+ *
+ * BSD license, See the LICENSE file for more information
+ *
+ * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef RANDOM_POLICY_H_
+#define RANDOM_POLICY_H_
+
+#include "ns3/random-variable.h"
+
+#include <boost/intrusive/options.hpp>
+#include <boost/intrusive/set.hpp>
+
+namespace ndn {
+namespace trie {
+
+/**
+ * @brief Traits for random replacement policy
+ */
+struct random_policy_traits
+{
+ /// @brief Name that can be used to identify the policy (e.g., for logging)
+ static std::string GetName () { return "Random"; }
+
+ struct policy_hook_type : public boost::intrusive::set_member_hook<> { uint32_t randomOrder; };
+
+ template<class Container>
+ struct container_hook
+ {
+ typedef boost::intrusive::member_hook< Container,
+ policy_hook_type,
+ &Container::policy_hook_ > type;
+ };
+
+ template<class Base,
+ class Container,
+ class Hook>
+ struct policy
+ {
+ static uint32_t& get_order (typename Container::iterator item)
+ {
+ return static_cast<typename policy_container::value_traits::hook_type*>
+ (policy_container::value_traits::to_node_ptr(*item))->randomOrder;
+ }
+
+ static const uint32_t& get_order (typename Container::const_iterator item)
+ {
+ return static_cast<const typename policy_container::value_traits::hook_type*>
+ (policy_container::value_traits::to_node_ptr(*item))->randomOrder;
+ }
+
+ template<class Key>
+ struct MemberHookLess
+ {
+ bool operator () (const Key &a, const Key &b) const
+ {
+ return get_order (&a) < get_order (&b);
+ }
+ };
+
+ typedef boost::intrusive::multiset< Container,
+ boost::intrusive::compare< MemberHookLess< Container > >,
+ Hook > policy_container;
+
+ // could be just typedef
+ class type : public policy_container
+ {
+ public:
+ typedef policy policy_base; // to get access to get_order methods from outside
+ typedef Container parent_trie;
+
+ type (Base &base)
+ : base_ (base)
+ , u_rand (0, std::numeric_limits<uint32_t>::max ())
+ , max_size_ (100)
+ {
+ }
+
+ inline void
+ update (typename parent_trie::iterator item)
+ {
+ // do nothing. it's random policy
+ }
+
+ inline bool
+ insert (typename parent_trie::iterator item)
+ {
+ get_order (item) = u_rand.GetValue ();
+
+ if (max_size_ != 0 && policy_container::size () >= max_size_)
+ {
+ if (MemberHookLess<Container>() (*item, *policy_container::begin ()))
+ {
+ // std::cout << "Cannot add. Signaling fail\n";
+ // just return false. Indicating that insert "failed"
+ return false;
+ }
+ else
+ {
+ // removing some random element
+ base_.erase (&(*policy_container::begin ()));
+ }
+ }
+
+ policy_container::insert (*item);
+ return true;
+ }
+
+ inline void
+ lookup (typename parent_trie::iterator item)
+ {
+ // do nothing. it's random policy
+ }
+
+ inline void
+ erase (typename parent_trie::iterator item)
+ {
+ policy_container::erase (policy_container::s_iterator_to (*item));
+ }
+
+ inline void
+ clear ()
+ {
+ policy_container::clear ();
+ }
+
+ inline void
+ set_max_size (size_t max_size)
+ {
+ max_size_ = max_size;
+ }
+
+ inline size_t
+ get_max_size () const
+ {
+ return max_size_;
+ }
+
+ private:
+ type () : base_(*((Base*)0)) { };
+
+ private:
+ Base &base_;
+ ns3::UniformVariable u_rand;
+ size_t max_size_;
+ };
+ };
+};
+
+} // trie
+} // ndn
+
+#endif // RANDOM_POLICY_H
diff --git a/ndn-cpp/trie/trie-with-policy.h b/ndn-cpp/trie/trie-with-policy.h
new file mode 100644
index 0000000..5a0d896
--- /dev/null
+++ b/ndn-cpp/trie/trie-with-policy.h
@@ -0,0 +1,263 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2013, Regents of the University of California
+ * Alexander Afanasyev
+ *
+ * BSD license, See the LICENSE file for more information
+ *
+ * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef TRIE_TRIE_WITH_POLICY_H_
+#define TRIE_TRIE_WITH_POLICY_H_
+
+#include "trie.h"
+
+namespace ndn {
+namespace trie {
+
+template<typename FullKey,
+ typename PayloadTraits,
+ typename PolicyTraits
+ >
+class trie_with_policy
+{
+public:
+ typedef trie< FullKey,
+ PayloadTraits,
+ typename PolicyTraits::policy_hook_type > parent_trie;
+
+ typedef typename parent_trie::iterator iterator;
+ typedef typename parent_trie::const_iterator const_iterator;
+ typedef typename parent_trie::payload_traits payload_traits;
+
+ typedef typename PolicyTraits::template policy<
+ trie_with_policy<FullKey, PayloadTraits, PolicyTraits>,
+ parent_trie,
+ typename PolicyTraits::template container_hook<parent_trie>::type >::type policy_container;
+
+ inline
+ trie_with_policy (size_t bucketSize = 10, size_t bucketIncrement = 10)
+ : trie_ ("", bucketSize, bucketIncrement)
+ , policy_ (*this)
+ {
+ }
+
+ inline std::pair< iterator, bool >
+ insert (const FullKey &key, typename PayloadTraits::insert_type payload)
+ {
+ std::pair<iterator, bool> item =
+ trie_.insert (key, payload);
+
+ if (item.second) // real insert
+ {
+ bool ok = policy_.insert (s_iterator_to (item.first));
+ if (!ok)
+ {
+ item.first->erase (); // cannot insert
+ return std::make_pair (end (), false);
+ }
+ }
+ else
+ {
+ return std::make_pair (s_iterator_to (item.first), false);
+ }
+
+ return item;
+ }
+
+ inline void
+ erase (const FullKey &key)
+ {
+ iterator foundItem, lastItem;
+ bool reachLast;
+ boost::tie (foundItem, reachLast, lastItem) = trie_.find (key);
+
+ if (!reachLast || lastItem->payload () == PayloadTraits::empty_payload)
+ return; // nothing to invalidate
+
+ erase (lastItem);
+ }
+
+ inline void
+ erase (iterator node)
+ {
+ if (node == end ()) return;
+
+ policy_.erase (s_iterator_to (node));
+ node->erase (); // will do cleanup here
+ }
+
+ inline void
+ clear ()
+ {
+ policy_.clear ();
+ trie_.clear ();
+ }
+
+ template<typename Modifier>
+ bool
+ modify (iterator position, Modifier mod)
+ {
+ if (position == end ()) return false;
+ if (position->payload () == PayloadTraits::empty_payload) return false;
+
+ mod (*position->payload ());
+ policy_.update (position);
+ return true;
+ }
+
+ /**
+ * @brief Find a node that has the exact match with the key
+ */
+ inline iterator
+ find_exact (const FullKey &key)
+ {
+ iterator foundItem, lastItem;
+ bool reachLast;
+ boost::tie (foundItem, reachLast, lastItem) = trie_.find (key);
+
+ if (!reachLast || lastItem->payload () == PayloadTraits::empty_payload)
+ return end ();
+
+ return lastItem;
+ }
+
+ /**
+ * @brief Find a node that has the longest common prefix with key (FIB/PIT lookup)
+ */
+ inline iterator
+ longest_prefix_match (const FullKey &key)
+ {
+ iterator foundItem, lastItem;
+ bool reachLast;
+ boost::tie (foundItem, reachLast, lastItem) = trie_.find (key);
+ if (foundItem != trie_.end ())
+ {
+ policy_.lookup (s_iterator_to (foundItem));
+ }
+ return foundItem;
+ }
+
+ /**
+ * @brief Find a node that has the longest common prefix with key (FIB/PIT lookup)
+ */
+ template<class Predicate>
+ inline iterator
+ longest_prefix_match_if (const FullKey &key, Predicate pred)
+ {
+ iterator foundItem, lastItem;
+ bool reachLast;
+ boost::tie (foundItem, reachLast, lastItem) = trie_.find_if (key, pred);
+ if (foundItem != trie_.end ())
+ {
+ policy_.lookup (s_iterator_to (foundItem));
+ }
+ return foundItem;
+ }
+
+ // /**
+ // * @brief Const version of the longest common prefix match
+ // * (semi-const, because there could be update of the policy anyways)
+ // */
+ // inline const_iterator
+ // longest_prefix_match (const FullKey &key) const
+ // {
+ // return static_cast<trie_with_policy*> (this)->longest_prefix_match (key);
+ // }
+
+ /**
+ * @brief Find a node that has prefix at least as the key (cache lookup)
+ */
+ inline iterator
+ deepest_prefix_match (const FullKey &key)
+ {
+ iterator foundItem, lastItem;
+ bool reachLast;
+ boost::tie (foundItem, reachLast, lastItem) = trie_.find (key);
+
+ // guard in case we don't have anything in the trie
+ if (lastItem == trie_.end ())
+ return trie_.end ();
+
+ if (reachLast)
+ {
+ if (foundItem == trie_.end ())
+ {
+ foundItem = lastItem->find (); // should be something
+ }
+ policy_.lookup (s_iterator_to (foundItem));
+ return foundItem;
+ }
+ else
+ { // couldn't find a node that has prefix at least as key
+ return trie_.end ();
+ }
+ }
+
+ /**
+ * @brief Find a node that has prefix at least as the key
+ */
+ template<class Predicate>
+ inline iterator
+ deepest_prefix_match (const FullKey &key, Predicate pred)
+ {
+ iterator foundItem, lastItem;
+ bool reachLast;
+ boost::tie (foundItem, reachLast, lastItem) = trie_.find (key);
+
+ // guard in case we don't have anything in the trie
+ if (lastItem == trie_.end ())
+ return trie_.end ();
+
+ if (reachLast)
+ {
+ foundItem = lastItem->find_if (pred); // may or may not find something
+ if (foundItem == trie_.end ())
+ {
+ return trie_.end ();
+ }
+ policy_.lookup (s_iterator_to (foundItem));
+ return foundItem;
+ }
+ else
+ { // couldn't find a node that has prefix at least as key
+ return trie_.end ();
+ }
+ }
+
+ iterator end () const
+ {
+ return 0;
+ }
+
+ const parent_trie &
+ getTrie () const { return trie_; }
+
+ parent_trie &
+ getTrie () { return trie_; }
+
+ const policy_container &
+ getPolicy () const { return policy_; }
+
+ policy_container &
+ 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_;
+ mutable policy_container policy_;
+};
+
+} // trie
+} // ndn
+
+#endif // TRIE_TRIE_WITH_POLICY_H_
diff --git a/ndn-cpp/trie/trie.h b/ndn-cpp/trie/trie.h
new file mode 100644
index 0000000..edc8a1b
--- /dev/null
+++ b/ndn-cpp/trie/trie.h
@@ -0,0 +1,636 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2013, Regents of the University of California
+ * Alexander Afanasyev
+ *
+ * BSD license, See the LICENSE file for more information
+ *
+ * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef NDN_TRIE_TRIE_H_
+#define NDN_TRIE_TRIE_H_
+
+#include <boost/intrusive/unordered_set.hpp>
+#include <boost/intrusive/list.hpp>
+#include <boost/intrusive/set.hpp>
+#include <boost/functional/hash.hpp>
+#include <boost/interprocess/smart_ptr/unique_ptr.hpp>
+#include <boost/tuple/tuple.hpp>
+#include <boost/foreach.hpp>
+#include <boost/mpl/if.hpp>
+
+#include "payload-traits/pointer.h"
+#include "payload-traits/ptr.h"
+
+namespace ndn {
+namespace trie {
+
+////////////////////////////////////////////////////
+// forward declarations
+//
+template<typename FullKey,
+ typename PayloadTraits,
+ typename PolicyHook >
+class trie;
+
+template<typename FullKey, typename PayloadTraits, typename PolicyHook>
+inline std::ostream&
+operator << (std::ostream &os,
+ const trie<FullKey, PayloadTraits, PolicyHook> &trie_node);
+
+template<typename FullKey, typename PayloadTraits, typename PolicyHook>
+bool
+operator== (const trie<FullKey, PayloadTraits, PolicyHook> &a,
+ const trie<FullKey, PayloadTraits, PolicyHook> &b);
+
+template<typename FullKey, typename PayloadTraits, typename PolicyHook >
+std::size_t
+hash_value (const trie<FullKey, PayloadTraits, PolicyHook> &trie_node);
+
+///////////////////////////////////////////////////
+// actual definition
+//
+template<class T, class NonConstT>
+class trie_iterator;
+
+template<class T>
+class trie_point_iterator;
+
+template<typename FullKey,
+ typename PayloadTraits,
+ typename PolicyHook >
+class trie
+{
+public:
+ typedef typename FullKey::partial_type Key;
+
+ typedef trie* iterator;
+ typedef const trie* const_iterator;
+
+ typedef trie_iterator<trie, trie> recursive_iterator;
+ typedef trie_iterator<const trie, trie> const_recursive_iterator;
+
+ typedef trie_point_iterator<trie> point_iterator;
+ typedef trie_point_iterator<const trie> const_point_iterator;
+
+ typedef PayloadTraits payload_traits;
+
+ inline
+ trie (const Key &key, size_t bucketSize = 10, size_t bucketIncrement = 10)
+ : key_ (key)
+ , initialBucketSize_ (bucketSize)
+ , bucketIncrement_ (bucketIncrement)
+ , bucketSize_ (initialBucketSize_)
+ , 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)
+ {
+ }
+
+ inline
+ ~trie ()
+ {
+ payload_ = PayloadTraits::empty_payload; // necessary for smart pointers...
+ children_.clear_and_dispose (trie_delete_disposer ());
+ }
+
+ void
+ clear ()
+ {
+ children_.clear_and_dispose (trie_delete_disposer ());
+ }
+
+ template<class Predicate>
+ void
+ clear_if (Predicate cond)
+ {
+ recursive_iterator trieNode (this);
+ recursive_iterator end (0);
+
+ while (trieNode != end)
+ {
+ if (cond (*trieNode))
+ {
+ trieNode = recursive_iterator (trieNode->erase ());
+ }
+ trieNode ++;
+ }
+ }
+
+ // actual entry
+ friend bool
+ operator== <> (const trie<FullKey, PayloadTraits, PolicyHook> &a,
+ const trie<FullKey, PayloadTraits, PolicyHook> &b);
+
+ friend std::size_t
+ hash_value <> (const trie<FullKey, PayloadTraits, PolicyHook> &trie_node);
+
+ inline std::pair<iterator, bool>
+ insert (const FullKey &key,
+ typename PayloadTraits::insert_type payload)
+ {
+ trie *trieNode = this;
+
+ BOOST_FOREACH (const Key &subkey, key)
+ {
+ typename unordered_set::iterator item = trieNode->children_.find (subkey);
+ if (item == trieNode->children_.end ())
+ {
+ trie *newNode = new trie (subkey, initialBucketSize_, bucketIncrement_);
+ // std::cout << "new " << newNode << "\n";
+ newNode->parent_ = trieNode;
+
+ if (trieNode->children_.size () >= trieNode->bucketSize_)
+ {
+ trieNode->bucketSize_ += trieNode->bucketIncrement_;
+ trieNode->bucketIncrement_ *= 2; // increase bucketIncrement exponentially
+
+ 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 =
+ trieNode->children_.insert (*newNode);
+
+ trieNode = &(*ret.first);
+ }
+ else
+ trieNode = &(*item);
+ }
+
+ if (trieNode->payload_ == PayloadTraits::empty_payload)
+ {
+ trieNode->payload_ = payload;
+ return std::make_pair (trieNode, true);
+ }
+ else
+ return std::make_pair (trieNode, false);
+ }
+
+ /**
+ * @brief Removes payload (if it exists) and if there are no children, prunes parents trie
+ */
+ inline iterator
+ erase ()
+ {
+ payload_ = PayloadTraits::empty_payload;
+ return prune ();
+ }
+
+ /**
+ * @brief Do exactly as erase, but without erasing the payload
+ */
+ inline iterator
+ prune ()
+ {
+ if (payload_ == PayloadTraits::empty_payload &&
+ children_.size () == 0)
+ {
+ if (parent_ == 0) return this;
+
+ trie *parent = parent_;
+ parent->children_.erase_and_dispose (*this, trie_delete_disposer ()); // delete this; basically, committing a suicide
+
+ return parent->prune ();
+ }
+ return this;
+ }
+
+ /**
+ * @brief Perform prune of the node, but without attempting to parent of the node
+ */
+ inline void
+ prune_node ()
+ {
+ if (payload_ == PayloadTraits::empty_payload &&
+ children_.size () == 0)
+ {
+ if (parent_ == 0) return;
+
+ trie *parent = parent_;
+ parent->children_.erase_and_dispose (*this, trie_delete_disposer ()); // delete this; basically, committing a suicide
+ }
+ }
+
+ // inline boost::tuple<const iterator, bool, const iterator>
+ // find (const FullKey &key) const
+ // {
+ // return const_cast<trie*> (this)->find (key);
+ // }
+
+ /**
+ * @brief Perform the longest prefix match
+ * @param key the key for which to perform the longest prefix match
+ *
+ * @return ->second is true if prefix in ->first is longer than key
+ */
+ inline boost::tuple<iterator, bool, iterator>
+ find (const FullKey &key)
+ {
+ trie *trieNode = this;
+ iterator foundNode = (payload_ != PayloadTraits::empty_payload) ? this : 0;
+ bool reachLast = true;
+
+ BOOST_FOREACH (const Key &subkey, key)
+ {
+ typename unordered_set::iterator item = trieNode->children_.find (subkey);
+ if (item == trieNode->children_.end ())
+ {
+ reachLast = false;
+ break;
+ }
+ else
+ {
+ trieNode = &(*item);
+
+ if (trieNode->payload_ != PayloadTraits::empty_payload)
+ foundNode = trieNode;
+ }
+ }
+
+ return boost::make_tuple (foundNode, reachLast, trieNode);
+ }
+
+ /**
+ * @brief Perform the longest prefix match satisfying preficate
+ * @param key the key for which to perform the longest prefix match
+ *
+ * @return ->second is true if prefix in ->first is longer than key
+ */
+ template<class Predicate>
+ inline boost::tuple<iterator, bool, iterator>
+ find_if (const FullKey &key, Predicate pred)
+ {
+ trie *trieNode = this;
+ iterator foundNode = (payload_ != PayloadTraits::empty_payload) ? this : 0;
+ bool reachLast = true;
+
+ BOOST_FOREACH (const Key &subkey, key)
+ {
+ typename unordered_set::iterator item = trieNode->children_.find (subkey);
+ if (item == trieNode->children_.end ())
+ {
+ reachLast = false;
+ break;
+ }
+ else
+ {
+ trieNode = &(*item);
+
+ if (trieNode->payload_ != PayloadTraits::empty_payload &&
+ pred (trieNode->payload_))
+ {
+ foundNode = trieNode;
+ }
+ }
+ }
+
+ return boost::make_tuple (foundNode, reachLast, trieNode);
+ }
+
+ /**
+ * @brief Find next payload of the sub-trie
+ * @returns end() or a valid iterator pointing to the trie leaf (order is not defined, enumeration )
+ */
+ inline iterator
+ find ()
+ {
+ if (payload_ != PayloadTraits::empty_payload)
+ return this;
+
+ typedef trie<FullKey, PayloadTraits, PolicyHook> trie;
+ for (typename trie::unordered_set::iterator subnode = children_.begin ();
+ subnode != children_.end ();
+ subnode++ )
+ // BOOST_FOREACH (trie &subnode, children_)
+ {
+ iterator value = subnode->find ();
+ if (value != 0)
+ return value;
+ }
+
+ return 0;
+ }
+
+ /**
+ * @brief Find next payload of the sub-trie satisfying the predicate
+ * @param pred predicate
+ * @returns end() or a valid iterator pointing to the trie leaf (order is not defined, enumeration )
+ */
+ template<class Predicate>
+ inline const iterator
+ find_if (Predicate pred)
+ {
+ if (payload_ != PayloadTraits::empty_payload && pred (payload_))
+ return this;
+
+ typedef trie<FullKey, PayloadTraits, PolicyHook> trie;
+ for (typename trie::unordered_set::iterator subnode = children_.begin ();
+ subnode != children_.end ();
+ subnode++ )
+ // BOOST_FOREACH (const trie &subnode, children_)
+ {
+ iterator value = subnode->find_if (pred);
+ if (value != 0)
+ return value;
+ }
+
+ return 0;
+ }
+
+ iterator end ()
+ {
+ return 0;
+ }
+
+ const_iterator end () const
+ {
+ return 0;
+ }
+
+ typename PayloadTraits::const_return_type
+ payload () const
+ {
+ return payload_;
+ }
+
+ typename PayloadTraits::return_type
+ payload ()
+ {
+ return payload_;
+ }
+
+ void
+ set_payload (typename PayloadTraits::insert_type payload)
+ {
+ payload_ = payload;
+ }
+
+ Key key () const
+ {
+ return key_;
+ }
+
+ inline void
+ PrintStat (std::ostream &os) const;
+
+private:
+ //The disposer object function
+ struct trie_delete_disposer
+ {
+ void operator() (trie *delete_this)
+ {
+ 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:
+ boost::intrusive::unordered_set_member_hook<> unordered_set_member_hook_;
+
+ // necessary typedefs
+ typedef trie self_type;
+ typedef boost::intrusive::member_hook< trie,
+ boost::intrusive::unordered_set_member_hook< >,
+ &trie::unordered_set_member_hook_ > member_hook;
+
+ typedef boost::intrusive::unordered_set< trie, member_hook > unordered_set;
+ typedef typename unordered_set::bucket_type bucket_type;
+ typedef typename unordered_set::bucket_traits bucket_traits;
+
+ template<class T, class NonConstT>
+ friend class trie_iterator;
+
+ template<class T>
+ friend class trie_point_iterator;
+
+ ////////////////////////////////////////////////
+ // Actual data
+ ////////////////////////////////////////////////
+
+ Key key_; ///< name component
+
+ size_t initialBucketSize_;
+ size_t bucketIncrement_;
+
+ size_t bucketSize_;
+ typedef boost::interprocess::unique_ptr< bucket_type, array_disposer<bucket_type> > buckets_array;
+ buckets_array buckets_;
+ unordered_set children_;
+
+ typename PayloadTraits::storage_type payload_;
+ trie *parent_; // to make cleaning effective
+};
+
+
+
+
+template<typename FullKey, typename PayloadTraits, typename PolicyHook>
+inline std::ostream&
+operator << (std::ostream &os, const trie<FullKey, PayloadTraits, PolicyHook> &trie_node)
+{
+ os << "# " << trie_node.key_ << ((trie_node.payload_ != PayloadTraits::empty_payload)?"*":"") << std::endl;
+ typedef trie<FullKey, PayloadTraits, PolicyHook> trie;
+
+ for (typename trie::unordered_set::const_iterator subnode = trie_node.children_.begin ();
+ subnode != trie_node.children_.end ();
+ subnode++ )
+ // BOOST_FOREACH (const trie &subnode, trie_node.children_)
+ {
+ os << "\"" << &trie_node << "\"" << " [label=\"" << trie_node.key_ << ((trie_node.payload_ != PayloadTraits::empty_payload)?"*":"") << "\"]\n";
+ os << "\"" << &(*subnode) << "\"" << " [label=\"" << subnode->key_ << ((subnode->payload_ != PayloadTraits::empty_payload)?"*":"") << "\"]""\n";
+
+ os << "\"" << &trie_node << "\"" << " -> " << "\"" << &(*subnode) << "\"" << "\n";
+ os << *subnode;
+ }
+
+ return os;
+}
+
+template<typename FullKey, typename PayloadTraits, typename PolicyHook>
+inline void
+trie<FullKey, PayloadTraits, PolicyHook>
+::PrintStat (std::ostream &os) const
+{
+ os << "# " << key_ << ((payload_ != PayloadTraits::empty_payload)?"*":"") << ": " << 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, PayloadTraits, PolicyHook> trie;
+ for (typename trie::unordered_set::const_iterator subnode = children_.begin ();
+ subnode != children_.end ();
+ subnode++ )
+ // BOOST_FOREACH (const trie &subnode, children_)
+ {
+ subnode->PrintStat (os);
+ }
+}
+
+
+template<typename FullKey, typename PayloadTraits, typename PolicyHook>
+inline bool
+operator == (const trie<FullKey, PayloadTraits, PolicyHook> &a,
+ const trie<FullKey, PayloadTraits, PolicyHook> &b)
+{
+ return a.key_ == b.key_;
+}
+
+template<typename FullKey, typename PayloadTraits, typename PolicyHook>
+inline std::size_t
+hash_value (const trie<FullKey, PayloadTraits, PolicyHook> &trie_node)
+{
+ return boost::hash_value (trie_node.key_);
+}
+
+
+
+template<class Trie, class NonConstTrie> // hack for boost < 1.47
+class trie_iterator
+{
+public:
+ trie_iterator () : trie_ (0) {}
+ trie_iterator (typename Trie::iterator item) : trie_ (item) {}
+ trie_iterator (Trie &item) : trie_ (&item) {}
+
+ Trie & operator* () { return *trie_; }
+ const Trie & operator* () const { return *trie_; }
+ Trie * operator-> () { return trie_; }
+ const Trie * operator-> () const { return trie_; }
+ bool operator== (trie_iterator<const Trie, NonConstTrie> &other) const { return (trie_ == other.trie_); }
+ bool operator== (trie_iterator<Trie, NonConstTrie> &other) { return (trie_ == other.trie_); }
+ bool operator!= (trie_iterator<const Trie, NonConstTrie> &other) const { return !(*this == other); }
+ bool operator!= (trie_iterator<Trie, NonConstTrie> &other) { return !(*this == other); }
+
+ trie_iterator<Trie,NonConstTrie> &
+ operator++ (int)
+ {
+ if (trie_->children_.size () > 0)
+ trie_ = &(*trie_->children_.begin ());
+ else
+ trie_ = goUp ();
+ return *this;
+ }
+
+ trie_iterator<Trie,NonConstTrie> &
+ operator++ ()
+ {
+ (*this)++;
+ return *this;
+ }
+
+private:
+ typedef typename boost::mpl::if_< boost::is_same<Trie, NonConstTrie>,
+ typename Trie::unordered_set::iterator,
+ typename Trie::unordered_set::const_iterator>::type set_iterator;
+
+ Trie* goUp ()
+ {
+ if (trie_->parent_ != 0)
+ {
+ // typename Trie::unordered_set::iterator item =
+ set_iterator item = const_cast<NonConstTrie*>(trie_)->parent_->children_.iterator_to (const_cast<NonConstTrie&> (*trie_));
+ item++;
+ if (item != trie_->parent_->children_.end ())
+ {
+ return &(*item);
+ }
+ else
+ {
+ trie_ = trie_->parent_;
+ return goUp ();
+ }
+ }
+ else
+ return 0;
+ }
+private:
+ Trie *trie_;
+};
+
+
+template<class Trie>
+class trie_point_iterator
+{
+private:
+ typedef typename boost::mpl::if_< boost::is_same<Trie, const Trie>,
+ typename Trie::unordered_set::const_iterator,
+ typename Trie::unordered_set::iterator>::type set_iterator;
+
+public:
+ trie_point_iterator () : trie_ (0) {}
+ trie_point_iterator (typename Trie::iterator item) : trie_ (item) {}
+ trie_point_iterator (Trie &item)
+ {
+ if (item.children_.size () != 0)
+ trie_ = &*item.children_.begin ();
+ else
+ trie_ = 0;
+ }
+
+ Trie & operator* () { return *trie_; }
+ const Trie & operator* () const { return *trie_; }
+ Trie * operator-> () { return trie_; }
+ const Trie * operator-> () const { return trie_; }
+ bool operator== (trie_point_iterator<const Trie> &other) const { return (trie_ == other.trie_); }
+ bool operator== (trie_point_iterator<Trie> &other) { return (trie_ == other.trie_); }
+ bool operator!= (trie_point_iterator<const Trie> &other) const { return !(*this == other); }
+ bool operator!= (trie_point_iterator<Trie> &other) { return !(*this == other); }
+
+ trie_point_iterator<Trie> &
+ operator++ (int)
+ {
+ if (trie_->parent_ != 0)
+ {
+ set_iterator item = trie_->parent_->children_.iterator_to (*trie_);
+ item ++;
+ if (item == trie_->parent_->children_.end ())
+ trie_ = 0;
+ else
+ trie_ = &*item;
+ }
+ else
+ {
+ trie_ = 0;
+ }
+ return *this;
+ }
+
+ trie_point_iterator<Trie> &
+ operator++ ()
+ {
+ (*this)++;
+ return *this;
+ }
+
+private:
+ Trie *trie_;
+};
+
+
+} // trie
+} // ndn
+
+#endif // NDN_TRIE_TRIE_H_