src: Updating code style to conform (more or less) to ndn-cxx style
Also, adding .clang-format that describes the applied style. Note that
this style requires a slightly customized version of clang-format.
diff --git a/utils/trie/aggregate-stats-policy.hpp b/utils/trie/aggregate-stats-policy.hpp
index ce466dd..b2cb0bd 100644
--- a/utils/trie/aggregate-stats-policy.hpp
+++ b/utils/trie/aggregate-stats-policy.hpp
@@ -32,80 +32,84 @@
* @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 aggregate_stats_policy_traits
-{
+struct aggregate_stats_policy_traits {
/// @brief Name that can be used to identify the policy (for NS-3 object model and logging)
- static std::string GetName () { return "AggregateStats"; }
- struct policy_hook_type { };
-
- template<class Container>
- struct container_hook
+ static std::string
+ GetName()
{
- struct type { };
+ return "AggregateStats";
+ }
+ struct policy_hook_type {
};
- template<class Base,
- class Container,
- class Hook>
- struct policy
- {
+ template<class Container>
+ struct container_hook {
+ struct 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
- {
+ class type {
public:
typedef Container parent_trie;
- type (Base &base)
- : base_ (base)
- , m_updates (0)
- , m_inserts (0)
- , m_lookups (0)
- , m_erases (0)
+ type(Base& base)
+ : base_(base)
+ , m_updates(0)
+ , m_inserts(0)
+ , m_lookups(0)
+ , m_erases(0)
{
}
inline void
- update (typename parent_trie::iterator item)
+ update(typename parent_trie::iterator item)
{
- m_updates ++;
+ m_updates++;
// do nothing
}
inline bool
- insert (typename parent_trie::iterator item)
+ insert(typename parent_trie::iterator item)
{
- m_inserts ++;
+ m_inserts++;
return true;
}
inline void
- lookup (typename parent_trie::iterator item)
+ lookup(typename parent_trie::iterator item)
{
- m_lookups ++;
+ m_lookups++;
}
inline void
- erase (typename parent_trie::iterator item)
+ erase(typename parent_trie::iterator item)
{
- m_erases ++;
+ m_erases++;
}
- inline void
- set_max_size (uint32_t) {}
+ inline void set_max_size(uint32_t)
+ {
+ }
inline uint32_t
- get_max_size () const { return 0; }
+ get_max_size() const
+ {
+ return 0;
+ }
inline void
- clear ()
+ clear()
{
// is called only at the end of simulation
}
inline void
- ResetStats ()
+ ResetStats()
{
m_updates = 0;
m_inserts = 0;
@@ -114,23 +118,36 @@
}
inline uint64_t
- GetUpdates () const { return m_updates; }
+ GetUpdates() const
+ {
+ return m_updates;
+ }
inline uint64_t
- GetInserts () const { return m_inserts; }
+ GetInserts() const
+ {
+ return m_inserts;
+ }
inline uint64_t
- GetLookups () const { return m_lookups; }
+ GetLookups() const
+ {
+ return m_lookups;
+ }
inline uint64_t
- GetErases () const { return m_erases; }
+ GetErases() const
+ {
+ return m_erases;
+ }
private:
- type () : base_(*((Base*)0)) { };
+ type()
+ : base_(*((Base*)0)){};
private:
- Base &base_;
-
+ Base& base_;
+
uint64_t m_updates;
uint64_t m_inserts;
uint64_t m_lookups;
diff --git a/utils/trie/counting-policy.hpp b/utils/trie/counting-policy.hpp
index 2c8656c..a44c290 100644
--- a/utils/trie/counting-policy.hpp
+++ b/utils/trie/counting-policy.hpp
@@ -32,76 +32,75 @@
* @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
-{
+struct counting_policy_traits {
/// @brief Name that can be used to identify the policy (for NS-3 object model and logging)
- static std::string GetName () { return "Counting"; }
-
- struct policy_hook_type : public boost::intrusive::list_member_hook<> {};
-
- template<class Container>
- struct container_hook
+ static std::string
+ GetName()
{
- // could be class/struct implementation
- typedef boost::intrusive::member_hook< Container,
- policy_hook_type,
- &Container::policy_hook_ > type;
+ return "Counting";
+ }
+
+ struct policy_hook_type : public boost::intrusive::list_member_hook<> {
};
- template<class Base,
- class Container,
- class Hook>
- struct policy
- {
- typedef typename boost::intrusive::list< Container, Hook > policy_container;
-
+ 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
- {
+ class type : public policy_container {
public:
typedef Container parent_trie;
- type (Base &base)
- : base_ (base)
+ type(Base& base)
+ : base_(base)
{
}
inline void
- update (typename parent_trie::iterator item)
+ update(typename parent_trie::iterator item)
{
// do nothing
}
-
+
inline bool
- insert (typename parent_trie::iterator item)
+ insert(typename parent_trie::iterator item)
{
- policy_container::push_back (*item);
+ policy_container::push_back(*item);
return true;
}
-
+
inline void
- lookup (typename parent_trie::iterator item)
+ lookup(typename parent_trie::iterator item)
{
// do nothing
}
-
+
inline void
- erase (typename parent_trie::iterator item)
+ erase(typename parent_trie::iterator item)
{
- policy_container::erase (policy_container::s_iterator_to (*item));
+ policy_container::erase(policy_container::s_iterator_to(*item));
}
inline void
- clear ()
+ clear()
{
- policy_container::clear ();
+ policy_container::clear();
}
private:
- type () : base_(*((Base*)0)) { };
+ type()
+ : base_(*((Base*)0)){};
private:
- Base &base_;
+ Base& base_;
};
};
};
diff --git a/utils/trie/detail/functor-hook.hpp b/utils/trie/detail/functor-hook.hpp
index f34969c..b0daadd 100644
--- a/utils/trie/detail/functor-hook.hpp
+++ b/utils/trie/detail/functor-hook.hpp
@@ -29,36 +29,43 @@
namespace detail {
template<class BaseHook, class ValueType, int N>
-struct FunctorHook
-{
+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)
+ 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
- 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_);
+ return &value.policy_hook_.template get<N>();
}
- static const_pointer to_value_ptr(const_hook_ptr n)
+
+ static const_hook_ptr
+ to_hook_ptr(const value_type& value)
{
- 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_);
+ 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_);
}
};
diff --git a/utils/trie/detail/multi-policy-container.hpp b/utils/trie/detail/multi-policy-container.hpp
index c1251e9..00bfbf1 100644
--- a/utils/trie/detail/multi-policy-container.hpp
+++ b/utils/trie/detail/multi-policy-container.hpp
@@ -29,144 +29,180 @@
namespace ndnSIM {
namespace detail {
-template< class Base, class Value >
-struct policy_wrap
-{
- policy_wrap (Base &base) : value_ (base) { }
+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) { }
+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)
+ update(typename Base::iterator item)
{
- Value::value_.update (item);
- Super::update (item);
+ Value::value_.update(item);
+ Super::update(item);
}
bool
- insert (typename Base::iterator item)
+ insert(typename Base::iterator item)
{
- bool ok = Value::value_.insert (item);
+ bool ok = Value::value_.insert(item);
if (!ok)
return false;
- ok = Super::insert (item);
- if (!ok)
- {
- Value::value_.erase (item);
- return false;
- }
+ ok = Super::insert(item);
+ if (!ok) {
+ Value::value_.erase(item);
+ return false;
+ }
return true;
}
void
- lookup (typename Base::iterator item)
+ lookup(typename Base::iterator item)
{
- Value::value_.lookup (item);
- Super::lookup (item);
+ Value::value_.lookup(item);
+ Super::lookup(item);
}
void
- erase (typename Base::iterator item)
+ erase(typename Base::iterator item)
{
- Value::value_.erase (item);
- Super::erase (item);
- }
+ Value::value_.erase(item);
+ Super::erase(item);
+ }
void
- clear ()
+ clear()
{
- Value::value_.clear ();
- Super::clear ();
+ Value::value_.clear();
+ Super::clear();
}
};
-template< class Base >
-struct empty_policy_wrap
-{
- empty_policy_wrap (Base &base) { }
+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 () {}
+ 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 >
+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;
+ : 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
+ 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 (); }
+ 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)
- { }
+ size_t
+ size() const
+ {
+ return this->get<0>().size();
+ }
+
+ multi_policy_container(Base& base)
+ : super(base)
+ {
+ }
template<int N>
- struct index
- {
+ struct index {
typedef typename boost::mpl::at_c<Vector, N>::type type;
};
-
+
template<class T>
- T &
- get ()
+ T&
+ get()
{
- return static_cast< policy_wrap<Base, T> &> (*this).value_;
+ return static_cast<policy_wrap<Base, T>&>(*this).value_;
}
template<class T>
- const T &
- get () const
+ const T&
+ get() const
{
- return static_cast< const policy_wrap<Base, T> &> (*this).value_;
+ return static_cast<const policy_wrap<Base, T>&>(*this).value_;
}
template<int N>
- typename boost::mpl::at_c<Vector, N>::type &
- get ()
+ 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_;
+ return static_cast<policy_wrap<Base, T>&>(*this).value_;
}
template<int N>
- const typename boost::mpl::at_c<Vector, N>::type &
- get () const
+ 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_;
+ return static_cast<const policy_wrap<Base, T>&>(*this).value_;
}
};
-
} // detail
} // ndnSIM
} // ndn
diff --git a/utils/trie/detail/multi-type-container.hpp b/utils/trie/detail/multi-type-container.hpp
index d4971c4..56dc89e 100644
--- a/utils/trie/detail/multi-type-container.hpp
+++ b/utils/trie/detail/multi-type-container.hpp
@@ -30,54 +30,51 @@
namespace ndnSIM {
namespace detail {
-template <class T>
-struct wrap
-{
+template<class T>
+struct wrap {
T value_;
};
-template< class Vector >
+template<class Vector>
struct multi_type_container
- : public boost::mpl::inherit_linearly< Vector, boost::mpl::inherit<wrap<boost::mpl::_2>, boost::mpl::_1 >
- >::type
-{
+ : public boost::mpl::inherit_linearly<Vector, boost::mpl::inherit<wrap<boost::mpl::_2>,
+ boost::mpl::_1>>::type {
template<int N>
- struct index
- {
+ struct index {
typedef typename boost::mpl::at_c<Vector, N>::type type;
};
-
+
template<class T>
- T &
- get ()
+ T&
+ get()
{
- return static_cast< wrap<T> &> (*this).value_;
+ return static_cast<wrap<T>&>(*this).value_;
}
template<class T>
- const T &
- get () const
+ 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_;
+ return static_cast<const wrap<T>&>(*this).value_;
}
template<int N>
- const typename boost::mpl::at_c<Vector, N>::type &
- get () const
+ typename boost::mpl::at_c<Vector, N>::type&
+ get()
{
typedef typename boost::mpl::at_c<Vector, N>::type T;
- return static_cast< const wrap<T> &> (*this).value_;
+ 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
diff --git a/utils/trie/empty-policy.hpp b/utils/trie/empty-policy.hpp
index c610717..7d077b6 100644
--- a/utils/trie/empty-policy.hpp
+++ b/utils/trie/empty-policy.hpp
@@ -28,29 +28,47 @@
/**
* @brief Traits for empty (bogus) replacement policy
*/
-struct empty_policy_traits
-{
+struct empty_policy_traits {
/// @brief Name that can be used to identify the policy (for NS-3 object model and logging)
- static std::string GetName () { return ""; }
+ static std::string
+ GetName()
+ {
+ return "";
+ }
typedef void* policy_hook_type;
- template<class Container> struct container_hook { typedef void* 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 () { }
+ 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()
+ {
+ }
};
};
};
diff --git a/utils/trie/fifo-policy.hpp b/utils/trie/fifo-policy.hpp
index 7ab4ec7..2527c16 100644
--- a/utils/trie/fifo-policy.hpp
+++ b/utils/trie/fifo-policy.hpp
@@ -31,94 +31,92 @@
/**
* @brief Traits for First In First Out replacement policy
*/
-struct fifo_policy_traits
-{
+struct fifo_policy_traits {
/// @brief Name that can be used to identify the policy (for NS-3 object model and logging)
- static std::string GetName () { return "Fifo"; }
-
- struct policy_hook_type : public boost::intrusive::list_member_hook<> {};
-
- template<class Container>
- struct container_hook
+ static std::string
+ GetName()
{
- // could be class/struct implementation
- typedef boost::intrusive::member_hook< Container,
- policy_hook_type,
- &Container::policy_hook_ > type;
+ return "Fifo";
+ }
+
+ struct policy_hook_type : public boost::intrusive::list_member_hook<> {
};
- template<class Base,
- class Container,
- class Hook>
- struct policy
- {
- typedef typename boost::intrusive::list< Container, Hook > policy_container;
-
+ 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
- {
+ class type : public policy_container {
public:
typedef Container parent_trie;
- type (Base &base)
- : base_ (base)
- , max_size_ (100)
+ type(Base& base)
+ : base_(base)
+ , max_size_(100)
{
}
inline void
- update (typename parent_trie::iterator item)
+ update(typename parent_trie::iterator item)
{
// do nothing
}
-
+
inline bool
- insert (typename parent_trie::iterator item)
+ 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);
+ 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)
+ lookup(typename parent_trie::iterator item)
{
// do nothing
}
-
+
inline void
- erase (typename parent_trie::iterator item)
+ erase(typename parent_trie::iterator item)
{
- policy_container::erase (policy_container::s_iterator_to (*item));
+ policy_container::erase(policy_container::s_iterator_to(*item));
}
inline void
- clear ()
+ clear()
{
- policy_container::clear ();
+ policy_container::clear();
}
inline void
- set_max_size (size_t max_size)
+ set_max_size(size_t max_size)
{
max_size_ = max_size;
}
inline size_t
- get_max_size () const
+ get_max_size() const
{
return max_size_;
}
private:
- type () : base_(*((Base*)0)) { };
+ type()
+ : base_(*((Base*)0)){};
private:
- Base &base_;
+ Base& base_;
size_t max_size_;
};
};
diff --git a/utils/trie/lfu-policy.hpp b/utils/trie/lfu-policy.hpp
index c6d6108..897dc49 100644
--- a/utils/trie/lfu-policy.hpp
+++ b/utils/trie/lfu-policy.hpp
@@ -31,124 +31,125 @@
/**
* @brief Traits for LFU replacement policy
*/
-struct lfu_policy_traits
-{
+struct lfu_policy_traits {
/// @brief Name that can be used to identify the policy (for NS-3 object model and 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
+ static std::string
+ GetName()
{
- typedef boost::intrusive::member_hook< Container,
- policy_hook_type,
- &Container::policy_hook_ > type;
+ return "Lfu";
+ }
+
+ struct policy_hook_type : public boost::intrusive::set_member_hook<> {
+ double frequency;
};
- template<class Base,
- class Container,
- class Hook>
- struct policy
- {
- static double& get_order (typename Container::iterator item)
+ 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;
+ 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)
+ 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;
+ 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
+ struct MemberHookLess {
+ bool
+ operator()(const Key& a, const Key& b) const
{
- return get_order (&a) < get_order (&b);
+ return get_order(&a) < get_order(&b);
}
};
- typedef boost::intrusive::multiset< Container,
- boost::intrusive::compare< MemberHookLess< Container > >,
- Hook > policy_container;
+ typedef boost::intrusive::multiset<Container,
+ boost::intrusive::compare<MemberHookLess<Container>>,
+ Hook> policy_container;
// could be just typedef
- class type : public policy_container
- {
+ 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)
+ type(Base& base)
+ : base_(base)
+ , max_size_(100)
{
}
inline void
- update (typename parent_trie::iterator item)
+ update(typename parent_trie::iterator item)
{
- policy_container::erase (policy_container::s_iterator_to (*item));
- get_order (item) += 1;
- policy_container::insert (*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)
+ insert(typename parent_trie::iterator item)
{
- get_order (item) = 0;
+ 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 ()));
- }
+ 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);
+ policy_container::insert(*item);
return true;
}
inline void
- lookup (typename parent_trie::iterator item)
+ lookup(typename parent_trie::iterator item)
{
- policy_container::erase (policy_container::s_iterator_to (*item));
- get_order (item) += 1;
- policy_container::insert (*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)
+ erase(typename parent_trie::iterator item)
{
- policy_container::erase (policy_container::s_iterator_to (*item));
+ policy_container::erase(policy_container::s_iterator_to(*item));
}
inline void
- clear ()
+ clear()
{
- policy_container::clear ();
+ policy_container::clear();
}
inline void
- set_max_size (size_t max_size)
+ set_max_size(size_t max_size)
{
max_size_ = max_size;
}
inline size_t
- get_max_size () const
+ get_max_size() const
{
return max_size_;
}
private:
- type () : base_(*((Base*)0)) { };
+ type()
+ : base_(*((Base*)0)){};
private:
- Base &base_;
+ Base& base_;
size_t max_size_;
};
};
diff --git a/utils/trie/lru-policy.hpp b/utils/trie/lru-policy.hpp
index a248117..77a65ca 100644
--- a/utils/trie/lru-policy.hpp
+++ b/utils/trie/lru-policy.hpp
@@ -31,99 +31,95 @@
/**
* @brief Traits for Least Recently Used replacement policy
*/
-struct lru_policy_traits
-{
+struct lru_policy_traits {
/// @brief Name that can be used to identify the policy (for NS-3 object model and logging)
- static std::string GetName () { return "Lru"; }
-
- struct policy_hook_type : public boost::intrusive::list_member_hook<> {};
-
- template<class Container>
- struct container_hook
+ static std::string
+ GetName()
{
- typedef boost::intrusive::member_hook< Container,
- policy_hook_type,
- &Container::policy_hook_ > type;
+ return "Lru";
+ }
+
+ struct policy_hook_type : public boost::intrusive::list_member_hook<> {
};
- template<class Base,
- class Container,
- class Hook>
- struct policy
- {
- typedef typename boost::intrusive::list< Container, Hook > policy_container;
-
+ 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
- {
+ class type : public policy_container {
public:
typedef Container parent_trie;
-
- type (Base &base)
- : base_ (base)
- , max_size_ (100)
+
+ type(Base& base)
+ : base_(base)
+ , max_size_(100)
{
}
inline void
- update (typename parent_trie::iterator item)
+ update(typename parent_trie::iterator item)
{
// do relocation
- policy_container::splice (policy_container::end (),
- *this,
- policy_container::s_iterator_to (*item));
+ policy_container::splice(policy_container::end(), *this,
+ policy_container::s_iterator_to(*item));
}
-
+
inline bool
- insert (typename parent_trie::iterator item)
+ 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);
+ 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)
+ 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));
+ policy_container::splice(policy_container::end(), *this,
+ policy_container::s_iterator_to(*item));
}
inline void
- clear ()
+ erase(typename parent_trie::iterator item)
{
- policy_container::clear ();
+ policy_container::erase(policy_container::s_iterator_to(*item));
}
inline void
- set_max_size (size_t max_size)
+ clear()
+ {
+ policy_container::clear();
+ }
+
+ inline void
+ set_max_size(size_t max_size)
{
max_size_ = max_size;
}
inline size_t
- get_max_size () const
+ get_max_size() const
{
return max_size_;
}
private:
- type () : base_(*((Base*)0)) { };
+ type()
+ : base_(*((Base*)0)){};
private:
- Base &base_;
+ Base& base_;
size_t max_size_;
};
};
diff --git a/utils/trie/multi-policy.hpp b/utils/trie/multi-policy.hpp
index 125df02..170f691 100644
--- a/utils/trie/multi-policy.hpp
+++ b/utils/trie/multi-policy.hpp
@@ -40,144 +40,148 @@
namespace ndnSIM {
template<typename Policies> // e.g., mpl::vector1< lru_policy_traits >
-struct multi_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;
-
+ 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
- {
+ 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;
+ 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
- {
+ 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;
+ 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
- {
+
+ 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)
+ type(Base& base)
+ : policy_container(base)
{
}
inline void
- update (typename parent_trie::iterator item)
+ update(typename parent_trie::iterator item)
{
- policy_container::update (item);
+ policy_container::update(item);
}
-
+
inline bool
- insert (typename parent_trie::iterator item)
+ 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 ();
+ return policy_container::insert(item);
}
- struct max_size_setter
+ inline void
+ lookup(typename parent_trie::iterator item)
{
- max_size_setter (policy_container &container, size_t size) : m_container (container), m_size (size) { }
-
- template< typename U > void operator() (U index)
+ 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)
{
- m_container.template get<U::value> ().set_max_size (m_size);
+ }
+
+ template<typename U>
+ void
+ operator()(U index)
+ {
+ m_container.template get<U::value>().set_max_size(m_size);
}
private:
- policy_container &m_container;
+ policy_container& m_container;
size_t m_size;
};
-
+
inline void
- set_max_size (size_t max_size)
+ 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));
+ 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
+ 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 ();
+ 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)
+ struct name_getter {
+ name_getter(std::string& name)
+ : m_name(name)
{
- if (!m_name.empty ())
- m_name += "::";
- m_name += boost::mpl::at_c< policy_traits, U::value >::type::GetName ();
}
- std::string &m_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 (for NS-3 object model and logging)
- static std::string GetName ()
+ 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));
-
+ boost::mpl::for_each<boost::mpl::range_c<int, 0, boost::mpl::size<policy_traits>::type::value>>(
+ name_getter(name));
+
return name;
}
};
diff --git a/utils/trie/payload-policy.hpp b/utils/trie/payload-policy.hpp
index a474afd..9193442 100644
--- a/utils/trie/payload-policy.hpp
+++ b/utils/trie/payload-policy.hpp
@@ -32,96 +32,88 @@
* @brief Traits for policy that keeps items in a sorted order using payload member
*/
template<class Member>
-struct payload_policy_traits
-{
- struct policy_hook_type : public boost::intrusive::set_member_hook<> {};
-
- template<class Container>
- struct container_hook
- {
- typedef boost::intrusive::member_hook< Container,
- policy_hook_type,
- &Container::policy_hook_ > type;
+struct payload_policy_traits {
+ struct policy_hook_type : public boost::intrusive::set_member_hook<> {
};
- template<class Base,
- class Container,
- class Hook>
- struct policy
- {
- typedef typename boost::intrusive::list< Container, Hook > policy_container;
-
+ 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
- {
+ class type : public policy_container {
public:
typedef Container parent_trie;
-
- type (Base &base)
- : base_ (base)
- , max_size_ (100)
+
+ type(Base& base)
+ : base_(base)
+ , max_size_(100)
{
}
inline void
- update (typename parent_trie::iterator item)
+ update(typename parent_trie::iterator item)
{
// do relocation
- policy_container::splice (policy_container::end (),
- *this,
- policy_container::s_iterator_to (*item));
+ policy_container::splice(policy_container::end(), *this,
+ policy_container::s_iterator_to(*item));
}
-
+
inline bool
- insert (typename parent_trie::iterator item)
+ insert(typename parent_trie::iterator item)
{
- if (policy_container::size () >= max_size_)
- {
- base_.erase (&(*policy_container::begin ()));
- }
-
- policy_container::push_back (*item);
+ if (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)
+ 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));
+ policy_container::splice(policy_container::end(), *this,
+ policy_container::s_iterator_to(*item));
}
inline void
- clear ()
+ erase(typename parent_trie::iterator item)
{
- policy_container::clear ();
+ policy_container::erase(policy_container::s_iterator_to(*item));
}
inline void
- set_max_size (size_t max_size)
+ clear()
+ {
+ policy_container::clear();
+ }
+
+ inline void
+ set_max_size(size_t max_size)
{
max_size_ = max_size;
}
inline size_t
- get_max_size () const
+ get_max_size() const
{
return max_size_;
}
private:
- type () : base_(*((Base*)0)) { };
+ type()
+ : base_(*((Base*)0)){};
private:
- Base &base_;
+ Base& base_;
size_t max_size_;
};
};
diff --git a/utils/trie/payload-with-policy.hpp b/utils/trie/payload-with-policy.hpp
index 7db278b..4010511 100644
--- a/utils/trie/payload-with-policy.hpp
+++ b/utils/trie/payload-with-policy.hpp
@@ -25,32 +25,29 @@
namespace ndn {
namespace ndnSIM {
-template<typename PayloadTraits,
- typename IndexTraits>
-class payload_with_index
-{
+template<typename PayloadTraits, typename IndexTraits>
+class payload_with_index {
public:
typedef PayloadTraits::pointer_type iterator;
-
- typedef typename IndexTraits::template index<
- PayloadTraits,
- typename IndexTraits::template container_hook<parent_trie>::type >::type index_container;
- inline
- payload_with_index ()
- : index_ (*this)
+ typedef typename IndexTraits::
+ template index<PayloadTraits,
+ typename IndexTraits::template container_hook<parent_trie>::type>::type
+ index_container;
+
+ inline payload_with_index()
+ : index_(*this)
{
}
- inline std::pair< iterator, bool >
- insert (typename iterator payload)
+ inline std::pair<iterator, bool>
+ insert(typename iterator payload)
{
- bool ok = policy_.insert (s_iterator_to (item.first));
- if (!ok)
- {
- item.first->erase (); // cannot insert
- return std::make_pair (end (), false);
- }
+ bool ok = policy_.insert(s_iterator_to(item.first));
+ if (!ok) {
+ item.first->erase(); // cannot insert
+ return std::make_pair(end(), false);
+ }
return item;
}
@@ -61,7 +58,7 @@
// iterator foundItem, lastItem;
// bool reachLast;
// boost::tie (foundItem, reachLast, lastItem) = trie_.find (key);
-
+
// if (!reachLast || lastItem->payload () == PayloadTraits::empty_payload)
// return; // nothing to invalidate
diff --git a/utils/trie/persistent-policy.hpp b/utils/trie/persistent-policy.hpp
index 9b706b0..c8f116c 100644
--- a/utils/trie/persistent-policy.hpp
+++ b/utils/trie/persistent-policy.hpp
@@ -32,84 +32,83 @@
* @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
+ * If maximum is reached, new entries will not be added and nothing will be removed from the
+ *container
*/
-struct persistent_policy_traits
-{
+struct persistent_policy_traits {
/// @brief Name that can be used to identify the policy (for NS-3 object model and logging)
- static std::string GetName () { return "Persistent"; }
-
- struct policy_hook_type : public boost::intrusive::list_member_hook<> {};
-
- template<class Container>
- struct container_hook
+ static std::string
+ GetName()
{
- typedef boost::intrusive::member_hook< Container,
- policy_hook_type,
- &Container::policy_hook_ > type;
+ return "Persistent";
+ }
+
+ struct policy_hook_type : public boost::intrusive::list_member_hook<> {
};
- template<class Base,
- class Container,
- class Hook>
- struct policy
- {
- typedef typename boost::intrusive::list< Container, Hook > policy_container;
-
+ 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
- {
+ class type : public policy_container {
public:
typedef Container parent_trie;
-
- type (Base &base)
- : base_ (base)
- , max_size_ (100) // when 0, policy is not enforced
+
+ type(Base& base)
+ : base_(base)
+ , max_size_(100) // when 0, policy is not enforced
{
}
inline void
- update (typename parent_trie::iterator item)
+ update(typename parent_trie::iterator item)
{
// do nothing
}
-
+
inline bool
- insert (typename parent_trie::iterator item)
+ insert(typename parent_trie::iterator item)
{
- if (max_size_ != 0 && policy_container::size () >= max_size_)
+ if (max_size_ != 0 && policy_container::size() >= max_size_)
return false;
-
- policy_container::push_back (*item);
+
+ policy_container::push_back(*item);
return true;
}
-
+
inline void
- lookup (typename parent_trie::iterator item)
+ lookup(typename parent_trie::iterator item)
{
// do nothing
}
-
+
inline void
- erase (typename parent_trie::iterator item)
+ erase(typename parent_trie::iterator item)
{
- policy_container::erase (policy_container::s_iterator_to (*item));
+ policy_container::erase(policy_container::s_iterator_to(*item));
}
inline void
- clear ()
+ clear()
{
- policy_container::clear ();
+ policy_container::clear();
}
inline void
- set_max_size (size_t max_size)
+ set_max_size(size_t max_size)
{
max_size_ = max_size;
}
inline size_t
- get_max_size () const
+ get_max_size() const
{
return max_size_;
}
@@ -118,7 +117,7 @@
// type () : base_(*((Base*)0)) { };
private:
- Base &base_;
+ Base& base_;
size_t max_size_;
};
};
diff --git a/utils/trie/random-policy.hpp b/utils/trie/random-policy.hpp
index 1a7308c..7264bed 100644
--- a/utils/trie/random-policy.hpp
+++ b/utils/trie/random-policy.hpp
@@ -33,130 +33,129 @@
/**
* @brief Traits for random replacement policy
*/
-struct random_policy_traits
-{
+struct random_policy_traits {
/// @brief Name that can be used to identify the policy (for NS-3 object model and 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
+ static std::string
+ GetName()
{
- typedef boost::intrusive::member_hook< Container,
- policy_hook_type,
- &Container::policy_hook_ > type;
+ return "Random";
+ }
+
+ struct policy_hook_type : public boost::intrusive::set_member_hook<> {
+ uint32_t randomOrder;
};
- template<class Base,
- class Container,
- class Hook>
- struct policy
- {
- static uint32_t& get_order (typename Container::iterator item)
+ 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;
+ 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)
+
+ 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;
+ 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
+ struct MemberHookLess {
+ bool
+ operator()(const Key& a, const Key& b) const
{
- return get_order (&a) < get_order (&b);
+ return get_order(&a) < get_order(&b);
}
};
- typedef boost::intrusive::multiset< Container,
- boost::intrusive::compare< MemberHookLess< Container > >,
- Hook > policy_container;
-
+ typedef boost::intrusive::multiset<Container,
+ boost::intrusive::compare<MemberHookLess<Container>>,
+ Hook> policy_container;
+
// could be just typedef
- class type : public policy_container
- {
+ 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)
+ 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)
+ update(typename parent_trie::iterator item)
{
// do nothing. it's random policy
}
-
+
inline bool
- insert (typename parent_trie::iterator item)
+ insert(typename parent_trie::iterator item)
{
- get_order (item) = u_rand.GetValue ();
+ 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 ()));
- }
+ 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);
+ policy_container::insert(*item);
return true;
}
-
+
inline void
- lookup (typename parent_trie::iterator item)
+ lookup(typename parent_trie::iterator item)
{
// do nothing. it's random policy
}
-
+
inline void
- erase (typename parent_trie::iterator item)
+ erase(typename parent_trie::iterator item)
{
- policy_container::erase (policy_container::s_iterator_to (*item));
+ policy_container::erase(policy_container::s_iterator_to(*item));
}
inline void
- clear ()
+ clear()
{
- policy_container::clear ();
+ policy_container::clear();
}
inline void
- set_max_size (size_t max_size)
+ set_max_size(size_t max_size)
{
max_size_ = max_size;
}
inline size_t
- get_max_size () const
+ get_max_size() const
{
return max_size_;
}
private:
- type () : base_(*((Base*)0)) { };
-
+ type()
+ : base_(*((Base*)0)){};
+
private:
- Base &base_;
+ Base& base_;
ns3::UniformVariable u_rand;
size_t max_size_;
};
diff --git a/utils/trie/trie-with-policy.hpp b/utils/trie/trie-with-policy.hpp
index f09f13b..790dd0f 100644
--- a/utils/trie/trie-with-policy.hpp
+++ b/utils/trie/trie-with-policy.hpp
@@ -27,93 +27,86 @@
namespace ndn {
namespace ndnSIM {
-template<typename FullKey,
- typename PayloadTraits,
- typename PolicyTraits
- >
-class trie_with_policy
-{
+template<typename FullKey, typename PayloadTraits, typename PolicyTraits>
+class trie_with_policy {
public:
- typedef trie< FullKey,
- PayloadTraits,
- typename PolicyTraits::policy_hook_type > parent_trie;
+ 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 PolicyTraits::template policy<
- trie_with_policy<FullKey, PayloadTraits, PolicyTraits>,
- parent_trie,
- typename PolicyTraits::template container_hook<parent_trie>::type >::type policy_container;
+ 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 = 1, size_t bucketIncrement = 1)
- : trie_ (name::Component (), bucketSize, bucketIncrement)
- , policy_ (*this)
+ inline trie_with_policy(size_t bucketSize = 1, size_t bucketIncrement = 1)
+ : trie_(name::Component(), bucketSize, bucketIncrement)
+ , policy_(*this)
{
}
- inline std::pair< iterator, bool >
- insert (const FullKey &key, typename PayloadTraits::insert_type payload)
+ inline std::pair<iterator, bool>
+ insert(const FullKey& key, typename PayloadTraits::insert_type payload)
{
- std::pair<iterator, bool> item =
- trie_.insert (key, 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);
- }
+ {
+ 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);
- }
+ }
+ else {
+ return std::make_pair(s_iterator_to(item.first), false);
+ }
return item;
}
inline void
- erase (const FullKey &key)
+ erase(const FullKey& key)
{
iterator foundItem, lastItem;
bool reachLast;
- boost::tie (foundItem, reachLast, lastItem) = trie_.find (key);
+ boost::tie(foundItem, reachLast, lastItem) = trie_.find(key);
- if (!reachLast || lastItem->payload () == PayloadTraits::empty_payload)
+ if (!reachLast || lastItem->payload() == PayloadTraits::empty_payload)
return; // nothing to invalidate
- erase (lastItem);
+ erase(lastItem);
}
inline void
- erase (iterator node)
+ erase(iterator node)
{
- if (node == end ()) return;
+ if (node == end())
+ return;
- policy_.erase (s_iterator_to (node));
- node->erase (); // will do cleanup here
+ policy_.erase(s_iterator_to(node));
+ node->erase(); // will do cleanup here
}
inline void
- clear ()
+ clear()
{
- policy_.clear ();
- trie_.clear ();
+ policy_.clear();
+ trie_.clear();
}
template<typename Modifier>
bool
- modify (iterator position, Modifier mod)
+ modify(iterator position, Modifier mod)
{
- if (position == end ()) return false;
- if (position->payload () == PayloadTraits::empty_payload) return false;
+ if (position == end())
+ return false;
+ if (position->payload() == PayloadTraits::empty_payload)
+ return false;
- mod (*position->payload ());
- policy_.update (position);
+ mod(*position->payload());
+ policy_.update(position);
return true;
}
@@ -121,14 +114,14 @@
* @brief Find a node that has the exact match with the key
*/
inline iterator
- find_exact (const FullKey &key)
+ find_exact(const FullKey& key)
{
iterator foundItem, lastItem;
bool reachLast;
- boost::tie (foundItem, reachLast, lastItem) = trie_.find (key);
+ boost::tie(foundItem, reachLast, lastItem) = trie_.find(key);
- if (!reachLast || lastItem->payload () == PayloadTraits::empty_payload)
- return end ();
+ if (!reachLast || lastItem->payload() == PayloadTraits::empty_payload)
+ return end();
return lastItem;
}
@@ -137,15 +130,14 @@
* @brief Find a node that has the longest common prefix with key (FIB/PIT lookup)
*/
inline iterator
- longest_prefix_match (const FullKey &key)
+ 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));
- }
+ boost::tie(foundItem, reachLast, lastItem) = trie_.find(key);
+ if (foundItem != trie_.end()) {
+ policy_.lookup(s_iterator_to(foundItem));
+ }
return foundItem;
}
@@ -154,15 +146,14 @@
*/
template<class Predicate>
inline iterator
- longest_prefix_match_if (const FullKey &key, Predicate pred)
+ 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));
- }
+ boost::tie(foundItem, reachLast, lastItem) = trie_.find_if(key, pred);
+ if (foundItem != trie_.end()) {
+ policy_.lookup(s_iterator_to(foundItem));
+ }
return foundItem;
}
@@ -180,29 +171,26 @@
* @brief Find a node that has prefix at least as the key (cache lookup)
*/
inline iterator
- deepest_prefix_match (const FullKey &key)
+ deepest_prefix_match(const FullKey& key)
{
iterator foundItem, lastItem;
bool reachLast;
- boost::tie (foundItem, reachLast, lastItem) = trie_.find (key);
+ 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 (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;
+ if (reachLast) {
+ if (foundItem == trie_.end()) {
+ foundItem = lastItem->find(); // should be something
}
- else
- { // couldn't find a node that has prefix at least as key
- 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();
+ }
}
/**
@@ -210,30 +198,27 @@
*/
template<class Predicate>
inline iterator
- deepest_prefix_match_if (const FullKey &key, Predicate pred)
+ deepest_prefix_match_if(const FullKey& key, Predicate pred)
{
iterator foundItem, lastItem;
bool reachLast;
- boost::tie (foundItem, reachLast, lastItem) = trie_.find (key);
+ 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 (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;
+ if (reachLast) {
+ foundItem = lastItem->find_if(pred); // may or may not find something
+ if (foundItem == trie_.end()) {
+ return trie_.end();
}
- else
- { // couldn't find a node that has prefix at least as key
- 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();
+ }
}
/**
@@ -244,51 +229,61 @@
*/
template<class Predicate>
inline iterator
- deepest_prefix_match_if_next_level (const FullKey &key, Predicate pred)
+ deepest_prefix_match_if_next_level(const FullKey& key, Predicate pred)
{
iterator foundItem, lastItem;
bool reachLast;
- boost::tie (foundItem, reachLast, lastItem) = trie_.find (key);
+ 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 (lastItem == trie_.end())
+ return trie_.end();
- if (reachLast)
- {
- foundItem = lastItem->find_if_next_level (pred); // may or may not find something
- if (foundItem == trie_.end ())
- {
- return trie_.end ();
- }
- policy_.lookup (s_iterator_to (foundItem));
- return foundItem;
+ if (reachLast) {
+ foundItem = lastItem->find_if_next_level(pred); // may or may not find something
+ if (foundItem == trie_.end()) {
+ return trie_.end();
}
- else
- { // couldn't find a node that has prefix at least as key
- 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
+
+ iterator
+ end() const
{
return 0;
}
- const parent_trie &
- getTrie () const { return trie_; }
+ const parent_trie&
+ getTrie() const
+ {
+ return trie_;
+ }
- parent_trie &
- getTrie () { return trie_; }
+ parent_trie&
+ getTrie()
+ {
+ return trie_;
+ }
- const policy_container &
- getPolicy () const { return policy_; }
+ const policy_container&
+ getPolicy() const
+ {
+ return policy_;
+ }
- policy_container &
- getPolicy () { return policy_; }
+ policy_container&
+ getPolicy()
+ {
+ return policy_;
+ }
static inline iterator
- s_iterator_to (typename parent_trie::iterator item)
+ s_iterator_to(typename parent_trie::iterator item)
{
if (item == 0)
return 0;
@@ -297,7 +292,7 @@
}
private:
- parent_trie trie_;
+ parent_trie trie_;
mutable policy_container policy_;
};
diff --git a/utils/trie/trie.hpp b/utils/trie/trie.hpp
index 1e37cbd..9afc8d1 100644
--- a/utils/trie/trie.hpp
+++ b/utils/trie/trie.hpp
@@ -40,33 +40,32 @@
// Allow customization for payload
//
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
+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 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)
+ 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 = 0;
+Payload* pointer_payload_traits<Payload, BasePayload>::empty_payload = 0;
template<typename Payload, typename BasePayload = Payload>
-struct smart_pointer_payload_traits
-{
- typedef Payload payload_type;
- typedef ns3::Ptr<Payload> storage_type;
- typedef ns3::Ptr<Payload> insert_type;
+struct smart_pointer_payload_traits {
+ typedef Payload payload_type;
+ typedef ns3::Ptr<Payload> storage_type;
+ typedef ns3::Ptr<Payload> insert_type;
- typedef ns3::Ptr<Payload> return_type;
+ typedef ns3::Ptr<Payload> return_type;
typedef ns3::Ptr<const Payload> const_return_type;
typedef ns3::Ptr<BasePayload> base_type;
@@ -76,51 +75,44 @@
};
template<typename Payload, typename BasePayload>
-ns3::Ptr<Payload>
-smart_pointer_payload_traits<Payload, BasePayload>::empty_payload = 0;
+ns3::Ptr<Payload> smart_pointer_payload_traits<Payload, BasePayload>::empty_payload = 0;
template<typename Payload, typename BasePayload = Payload>
-struct non_pointer_traits
-{
- typedef Payload payload_type;
- typedef Payload storage_type;
- typedef const Payload & insert_type; // nothing to insert
+struct non_pointer_traits {
+ typedef Payload payload_type;
+ typedef Payload storage_type;
+ typedef const Payload& insert_type; // nothing to insert
- typedef Payload& return_type;
- typedef const Payload & const_return_type;
+ typedef Payload& return_type;
+ typedef const Payload& const_return_type;
- typedef BasePayload& base_type;
+ typedef BasePayload& base_type;
typedef const BasePayload& const_base_type;
static Payload empty_payload;
};
template<typename Payload, typename BasePayload>
-Payload
-non_pointer_traits<Payload, BasePayload>::empty_payload = Payload ();
-
+Payload non_pointer_traits<Payload, BasePayload>::empty_payload = Payload();
////////////////////////////////////////////////////
// forward declarations
//
-template<typename FullKey,
- typename PayloadTraits,
- typename PolicyHook >
+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);
+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);
+operator==(const trie<FullKey, PayloadTraits, PolicyHook>& a,
+ const trie<FullKey, PayloadTraits, PolicyHook>& b);
-template<typename FullKey, typename PayloadTraits, typename PolicyHook >
+template<typename FullKey, typename PayloadTraits, typename PolicyHook>
std::size_t
-hash_value (const trie<FullKey, PayloadTraits, PolicyHook> &trie_node);
+hash_value(const trie<FullKey, PayloadTraits, PolicyHook>& trie_node);
///////////////////////////////////////////////////
// actual definition
@@ -131,15 +123,12 @@
template<class T>
class trie_point_iterator;
-template<typename FullKey,
- typename PayloadTraits,
- typename PolicyHook >
-class trie
-{
+template<typename FullKey, typename PayloadTraits, typename PolicyHook>
+class trie {
public:
typedef typename FullKey::partial_type Key;
- typedef trie* iterator;
+ typedef trie* iterator;
typedef const trie* const_iterator;
typedef trie_iterator<trie, trie> recursive_iterator;
@@ -150,126 +139,119 @@
typedef PayloadTraits payload_traits;
- inline
- trie (const Key &key, size_t bucketSize = 1, size_t bucketIncrement = 1)
- : 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(const Key& key, size_t bucketSize = 1, size_t bucketIncrement = 1)
+ : 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 ()
+ inline ~trie()
{
payload_ = PayloadTraits::empty_payload; // necessary for smart pointers...
- children_.clear_and_dispose (trie_delete_disposer ());
+ children_.clear_and_dispose(trie_delete_disposer());
}
void
- clear ()
+ clear()
{
- children_.clear_and_dispose (trie_delete_disposer ());
+ children_.clear_and_dispose(trie_delete_disposer());
}
template<class Predicate>
void
- clear_if (Predicate cond)
+ clear_if(Predicate cond)
{
- recursive_iterator trieNode (this);
- recursive_iterator end (0);
+ recursive_iterator trieNode(this);
+ recursive_iterator end(0);
- while (trieNode != end)
- {
- if (cond (*trieNode))
- {
- trieNode = recursive_iterator (trieNode->erase ());
- }
- trieNode ++;
+ 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 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);
+ hash_value<>(const trie<FullKey, PayloadTraits, PolicyHook>& trie_node);
inline std::pair<iterator, bool>
- insert (const FullKey &key,
- typename PayloadTraits::insert_type payload)
+ insert(const FullKey& key, typename PayloadTraits::insert_type payload)
{
- trie *trieNode = this;
+ 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;
+ 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
+ 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);
- }
+ 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);
+ std::pair<typename unordered_set::iterator, bool> ret =
+ trieNode->children_.insert(*newNode);
- trieNode = &(*ret.first);
- }
- else
- trieNode = &(*item);
+ trieNode = &(*ret.first);
}
+ else
+ trieNode = &(*item);
+ }
- if (trieNode->payload_ == PayloadTraits::empty_payload)
- {
- trieNode->payload_ = payload;
- return std::make_pair (trieNode, true);
- }
+ if (trieNode->payload_ == PayloadTraits::empty_payload) {
+ trieNode->payload_ = payload;
+ return std::make_pair(trieNode, true);
+ }
else
- return std::make_pair (trieNode, false);
+ return std::make_pair(trieNode, false);
}
/**
* @brief Removes payload (if it exists) and if there are no children, prunes parents trie
*/
inline iterator
- erase ()
+ erase()
{
payload_ = PayloadTraits::empty_payload;
- return prune ();
+ return prune();
}
/**
* @brief Do exactly as erase, but without erasing the payload
*/
inline iterator
- prune ()
+ prune()
{
- if (payload_ == PayloadTraits::empty_payload &&
- children_.size () == 0)
- {
- if (parent_ == 0) return this;
+ 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
+ trie* parent = parent_;
+ parent->children_
+ .erase_and_dispose(*this,
+ trie_delete_disposer()); // delete this; basically, committing a suicide
- return parent->prune ();
- }
+ return parent->prune();
+ }
return this;
}
@@ -277,16 +259,17 @@
* @brief Perform prune of the node, but without attempting to parent of the node
*/
inline void
- prune_node ()
+ prune_node()
{
- if (payload_ == PayloadTraits::empty_payload &&
- children_.size () == 0)
- {
- if (parent_ == 0) return;
+ 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
- }
+ 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>
@@ -302,30 +285,27 @@
* @return ->second is true if prefix in ->first is longer than key
*/
inline boost::tuple<iterator, bool, iterator>
- find (const FullKey &key)
+ find(const FullKey& key)
{
- trie *trieNode = this;
+ 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;
- }
+ 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);
- return boost::make_tuple (foundNode, reachLast, trieNode);
+ if (trieNode->payload_ != PayloadTraits::empty_payload)
+ foundNode = trieNode;
+ }
+ }
+
+ return boost::make_tuple(foundNode, reachLast, trieNode);
}
/**
@@ -336,55 +316,50 @@
*/
template<class Predicate>
inline boost::tuple<iterator, bool, iterator>
- find_if (const FullKey &key, Predicate pred)
+ find_if(const FullKey& key, Predicate pred)
{
- trie *trieNode = this;
+ 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;
- }
- }
+ 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);
- return boost::make_tuple (foundNode, reachLast, trieNode);
+ 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 )
+ * @returns end() or a valid iterator pointing to the trie leaf (order is not defined, enumeration
+ * )
*/
inline iterator
- find ()
+ 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;
- }
+ 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;
}
@@ -392,25 +367,25 @@
/**
* @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 )
+ * @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)
+ find_if(Predicate pred)
{
- if (payload_ != PayloadTraits::empty_payload && pred (payload_))
+ 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;
- }
+ 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;
}
@@ -421,84 +396,83 @@
*
* This version check predicate only for the next level children
*
- * @returns end() or a valid iterator pointing to the trie leaf (order is not defined, enumeration )
+ * @returns end() or a valid iterator pointing to the trie leaf (order is not defined, enumeration
+ *)
*/
template<class Predicate>
inline const iterator
- find_if_next_level (Predicate pred)
+ find_if_next_level(Predicate pred)
{
typedef trie<FullKey, PayloadTraits, PolicyHook> trie;
- for (typename trie::unordered_set::iterator subnode = children_.begin ();
- subnode != children_.end ();
- subnode++ )
- {
- if (pred (subnode->key ()))
- {
- return subnode->find ();
- }
+ for (typename trie::unordered_set::iterator subnode = children_.begin();
+ subnode != children_.end(); subnode++) {
+ if (pred(subnode->key())) {
+ return subnode->find();
}
+ }
return 0;
}
- iterator end ()
+ iterator
+ end()
{
return 0;
}
- const_iterator end () const
+ const_iterator
+ end() const
{
return 0;
}
typename PayloadTraits::const_return_type
- payload () const
+ payload() const
{
return payload_;
}
typename PayloadTraits::return_type
- payload ()
+ payload()
{
return payload_;
}
void
- set_payload (typename PayloadTraits::insert_type payload)
+ set_payload(typename PayloadTraits::insert_type payload)
{
payload_ = payload;
}
- Key key () const
+ Key
+ key() const
{
return key_;
}
inline void
- PrintStat (std::ostream &os) const;
+ PrintStat(std::ostream& os) const;
private:
- //The disposer object function
- struct trie_delete_disposer
- {
- void operator() (trie *delete_this)
+ // 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)
+ struct array_disposer {
+ void
+ operator()(D* array)
{
- delete [] array;
+ delete[] array;
}
};
- friend
- std::ostream&
- operator<< < > (std::ostream &os, const trie &trie_node);
+ friend std::ostream& operator<<<>(std::ostream& os, const trie& trie_node);
public:
PolicyHook policy_hook_;
@@ -508,12 +482,11 @@
// 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::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 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>
@@ -532,204 +505,267 @@
size_t bucketIncrement_;
size_t bucketSize_;
- typedef boost::interprocess::unique_ptr< bucket_type, array_disposer<bucket_type> > buckets_array;
+ 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
+ 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)
+operator<<(std::ostream& os, const trie<FullKey, PayloadTraits, PolicyHook>& trie_node)
{
- os << "# " << trie_node.key_ << ((trie_node.payload_ != PayloadTraits::empty_payload)?"*":"") << std::endl;
+ 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++ )
+ 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 << "\""
+ << " [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;
- }
+ 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
+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 << "# " << 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++ )
+ for (typename trie::unordered_set::const_iterator subnode = children_.begin();
+ subnode != children_.end(); subnode++)
// BOOST_FOREACH (const trie &subnode, children_)
- {
- subnode->PrintStat (os);
- }
+ {
+ 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)
+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)
+hash_value(const trie<FullKey, PayloadTraits, PolicyHook>& trie_node)
{
- return boost::hash_value (trie_node.key_);
+ return boost::hash_value(trie_node.key_);
}
-
-
template<class Trie, class NonConstTrie> // hack for boost < 1.47
-class trie_iterator
-{
+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)
+ trie_iterator()
+ : trie_(0)
{
- if (trie_->children_.size () > 0)
- trie_ = &(*trie_->children_.begin ());
+ }
+ 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 ();
+ trie_ = goUp();
return *this;
}
- trie_iterator<Trie,NonConstTrie> &
- operator++ ()
+ 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;
+ 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 ()
+ 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 ();
- }
+ 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_;
+ Trie* trie_;
};
-
template<class Trie>
-class trie_point_iterator
-{
+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;
+ 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)
+ trie_point_iterator()
+ : trie_(0)
{
- if (item.children_.size () != 0)
- trie_ = &*item.children_.begin ();
+ }
+ 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)
+ Trie& operator*()
{
- 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
- {
+ 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++ ()
+ trie_point_iterator<Trie>&
+ operator++()
{
(*this)++;
return *this;
}
private:
- Trie *trie_;
+ Trie* trie_;
};
-
} // ndnSIM
} // ndn
} // ns3