Some progress on CcnxPit. Partially working
diff --git a/utils/empty-policy.h b/utils/empty-policy.h
index c5f324c..a04507d 100644
--- a/utils/empty-policy.h
+++ b/utils/empty-policy.h
@@ -24,6 +24,9 @@
namespace ndnSIM
{
+/**
+ * @brief Traits for empty (bogus) replacement policy
+ */
struct empty_policy_traits
{
typedef void* policy_hook_type;
diff --git a/utils/fifo-policy.h b/utils/fifo-policy.h
index 2dccbe4..7a61721 100644
--- a/utils/fifo-policy.h
+++ b/utils/fifo-policy.h
@@ -27,6 +27,9 @@
namespace ndnSIM
{
+/**
+ * @brief Traits for First In First Out replacement policy
+ */
struct fifo_policy_traits
{
struct policy_hook_type : public boost::intrusive::list_member_hook<> {};
diff --git a/utils/lru-policy.h b/utils/lru-policy.h
index 077d602..92a9953 100644
--- a/utils/lru-policy.h
+++ b/utils/lru-policy.h
@@ -27,6 +27,9 @@
namespace ndnSIM
{
+/**
+ * @brief Traits for Least Recently Used replacement policy
+ */
struct lru_policy_traits
{
struct policy_hook_type : public boost::intrusive::list_member_hook<> {};
diff --git a/utils/payload-policy.h b/utils/payload-policy.h
new file mode 100644
index 0000000..5eb384a
--- /dev/null
+++ b/utils/payload-policy.h
@@ -0,0 +1,131 @@
+/* -*- 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 PAYLOAD_POLICY_H_
+#define PAYLOAD_POLICY_H_
+
+#include <boost/intrusive/options.hpp>
+#include <boost/intrusive/list.hpp>
+
+namespace ndnSIM
+{
+
+/**
+ * @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;
+ };
+
+ 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 (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_;
+ };
+ };
+};
+
+} // ndnSIM
+
+#endif // PAYLOAD_POLICY_H
diff --git a/utils/persistent-policy.h b/utils/persistent-policy.h
new file mode 100644
index 0000000..fb72864
--- /dev/null
+++ b/utils/persistent-policy.h
@@ -0,0 +1,125 @@
+/* -*- 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 PERSISTENT_POLICY_H_
+#define PERSISTENT_POLICY_H_
+
+#include <boost/intrusive/options.hpp>
+#include <boost/intrusive/list.hpp>
+
+namespace ndnSIM
+{
+
+/**
+ * @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
+{
+ 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_;
+ };
+ };
+};
+
+} // ndnSIM
+
+#endif // PERSISTENT_POLICY_H_
diff --git a/utils/random-policy.h b/utils/random-policy.h
index 7a96712..288cd74 100644
--- a/utils/random-policy.h
+++ b/utils/random-policy.h
@@ -29,6 +29,9 @@
namespace ndnSIM
{
+/**
+ * @brief Traits for random replacement policy
+ */
struct random_policy_traits
{
struct policy_hook_type : public boost::intrusive::set_member_hook<> { uint32_t randomOrder; };
diff --git a/utils/trie-with-policy.h b/utils/trie-with-policy.h
index a2be29a..ea194b3 100644
--- a/utils/trie-with-policy.h
+++ b/utils/trie-with-policy.h
@@ -34,7 +34,6 @@
{
public:
typedef trie< FullKey,
- typename PayloadTraits::payload_type,
PayloadTraits,
typename PolicyTraits::policy_hook_type > parent_trie;
@@ -133,6 +132,16 @@
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)
*/
@@ -221,7 +230,7 @@
private:
parent_trie trie_;
- policy_container policy_;
+ mutable policy_container policy_;
};
} // ndnSIM
diff --git a/utils/trie.h b/utils/trie.h
index 1b2056e..50288af 100644
--- a/utils/trie.h
+++ b/utils/trie.h
@@ -71,24 +71,23 @@
// forward declarations
//
template<typename FullKey,
- typename Payload,
typename PayloadTraits,
typename PolicyHook >
class trie;
-template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook>
+template<typename FullKey, typename PayloadTraits, typename PolicyHook>
inline std::ostream&
operator << (std::ostream &os,
- const trie<FullKey, Payload, PayloadTraits, PolicyHook> &trie_node);
+ const trie<FullKey, PayloadTraits, PolicyHook> &trie_node);
-template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook>
+template<typename FullKey, typename PayloadTraits, typename PolicyHook>
bool
-operator== (const trie<FullKey, Payload, PayloadTraits, PolicyHook> &a,
- const trie<FullKey, Payload, PayloadTraits, PolicyHook> &b);
+operator== (const trie<FullKey, PayloadTraits, PolicyHook> &a,
+ const trie<FullKey, PayloadTraits, PolicyHook> &b);
-template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook >
+template<typename FullKey, typename PayloadTraits, typename PolicyHook >
std::size_t
-hash_value (const trie<FullKey, Payload, PayloadTraits, PolicyHook> &trie_node);
+hash_value (const trie<FullKey, PayloadTraits, PolicyHook> &trie_node);
///////////////////////////////////////////////////
// actual definition
@@ -97,7 +96,7 @@
class trie_iterator;
template<typename FullKey,
- typename Payload, typename PayloadTraits,
+ typename PayloadTraits,
typename PolicyHook >
class trie
{
@@ -109,6 +108,8 @@
typedef trie_iterator<trie> recursive_iterator;
typedef trie_iterator<const trie> const_recursive_iterator;
+
+ typedef PayloadTraits payload_traits;
inline
trie (const Key &key, size_t bucketSize = 10, size_t bucketIncrement = 10)
@@ -155,11 +156,11 @@
// actual entry
friend bool
- operator== <> (const trie<FullKey, Payload, PayloadTraits, PolicyHook> &a,
- const trie<FullKey, Payload, PayloadTraits, PolicyHook> &b);
+ operator== <> (const trie<FullKey, PayloadTraits, PolicyHook> &a,
+ const trie<FullKey, PayloadTraits, PolicyHook> &b);
friend std::size_t
- hash_value <> (const trie<FullKey, Payload, PayloadTraits, PolicyHook> &trie_node);
+ hash_value <> (const trie<FullKey, PayloadTraits, PolicyHook> &trie_node);
inline std::pair<iterator, bool>
insert (const FullKey &key,
@@ -231,11 +232,11 @@
return this;
}
- inline boost::tuple<const iterator, bool, const iterator>
- find (const FullKey &key) const
- {
- return const_cast<trie*> (this)->find (key);
- }
+ // 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
@@ -280,7 +281,7 @@
if (payload_ != PayloadTraits::empty_payload)
return this;
- typedef trie<FullKey, Payload, PayloadTraits, PolicyHook> trie;
+ typedef trie<FullKey, PayloadTraits, PolicyHook> trie;
for (typename trie::unordered_set::iterator subnode = children_.begin ();
subnode != children_.end ();
subnode++ )
@@ -300,13 +301,13 @@
* @returns end() or a valid iterator pointing to the trie leaf (order is not defined, enumeration )
*/
template<class Predicate>
- inline iterator
+ inline const iterator
find_if (Predicate pred)
{
if (payload_ != PayloadTraits::empty_payload && pred (payload_))
return this;
- typedef trie<FullKey, Payload, PayloadTraits, PolicyHook> trie;
+ typedef trie<FullKey, PayloadTraits, PolicyHook> trie;
for (typename trie::unordered_set::iterator subnode = children_.begin ();
subnode != children_.end ();
subnode++ )
@@ -414,12 +415,12 @@
-template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook>
+template<typename FullKey, typename PayloadTraits, typename PolicyHook>
inline std::ostream&
-operator << (std::ostream &os, const trie<FullKey, Payload, PayloadTraits, PolicyHook> &trie_node)
+operator << (std::ostream &os, const trie<FullKey, PayloadTraits, PolicyHook> &trie_node)
{
os << "# " << trie_node.key_ << ((trie_node.payload_ != 0)?"*":"") << std::endl;
- typedef trie<FullKey, Payload, PayloadTraits, PolicyHook> trie;
+ typedef trie<FullKey, PayloadTraits, PolicyHook> trie;
for (typename trie::unordered_set::const_iterator subnode = trie_node.children_.begin ();
subnode != trie_node.children_.end ();
@@ -436,9 +437,9 @@
return os;
}
-template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook>
+template<typename FullKey, typename PayloadTraits, typename PolicyHook>
inline void
-trie<FullKey, Payload, PayloadTraits, PolicyHook>
+trie<FullKey, PayloadTraits, PolicyHook>
::PrintStat (std::ostream &os) const
{
os << "# " << key_ << ((payload_ != 0)?"*":"") << ": " << children_.size() << " children" << std::endl;
@@ -450,7 +451,7 @@
}
os << "\n";
- typedef trie<FullKey, Payload, PayloadTraits, PolicyHook> trie;
+ typedef trie<FullKey, PayloadTraits, PolicyHook> trie;
for (typename trie::unordered_set::const_iterator subnode = children_.begin ();
subnode != children_.end ();
subnode++ )
@@ -461,17 +462,17 @@
}
-template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook>
+template<typename FullKey, typename PayloadTraits, typename PolicyHook>
inline bool
-operator == (const trie<FullKey, Payload, PayloadTraits, PolicyHook> &a,
- const trie<FullKey, Payload, 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 Payload, typename PayloadTraits, typename PolicyHook>
+template<typename FullKey, typename PayloadTraits, typename PolicyHook>
inline std::size_t
-hash_value (const trie<FullKey, Payload, PayloadTraits, PolicyHook> &trie_node)
+hash_value (const trie<FullKey, PayloadTraits, PolicyHook> &trie_node)
{
return boost::hash_value (trie_node.key_);
}