New implementation of FIB seems to be working now
diff --git a/apps/ccnx-producer.cc b/apps/ccnx-producer.cc
index 73ab8b7..ff30071 100644
--- a/apps/ccnx-producer.cc
+++ b/apps/ccnx-producer.cc
@@ -84,9 +84,12 @@
CcnxApp::StartApplication ();
+ NS_LOG_DEBUG ("NodeID: " << GetNode ()->GetId ());
+
Ptr<CcnxFib> fib = GetNode ()->GetObject<CcnxFib> ();
+
CcnxFib::iterator fibEntry = fib->Add (m_prefix, m_face, 0);
-
+
// make face green, so it will be used primarily
StaticCast<CcnxFibImpl> (fib)->modify (fibEntry,
ll::bind (&CcnxFibEntry::UpdateStatus,
diff --git a/examples/trie.cc b/examples/trie.cc
index bdbc328..7ec0c40 100644
--- a/examples/trie.cc
+++ b/examples/trie.cc
@@ -26,6 +26,9 @@
#include "../utils/fifo-policy.h"
#include "../utils/multi-policy.h"
+#include <boost/lexical_cast.hpp>
+
+using namespace std;
using namespace ns3;
using namespace ndnSIM;
using namespace boost;
@@ -55,44 +58,67 @@
CommandLine args;
args.Parse (argc, argv);
- typedef trie_with_policy<
- ns3::CcnxNameComponents,
- smart_pointer_payload_traits<Integer>,
- multi_policy_traits<
- mpl::vector2<lru_policy_traits,random_policy_traits>
- > > trie;
+ // typedef trie_with_policy<
+ // ns3::CcnxNameComponents,
+ // smart_pointer_payload_traits<Integer>,
+ // multi_policy_traits<
+ // mpl::vector2<lru_policy_traits,random_policy_traits>
+ // > > trie;
- trie x;
- x.getPolicy ().get<0> ().set_max_size (100);
- x.getPolicy ().get<1> ().set_max_size (3);
- // // x.getPolicy ().get<1> ().set_max_size (3);
- // // // x.getPolicy ().get1 ().set_max_size (10);
- // // // x.getPolicy ().get2 ().set_max_size (3);
+ // trie x;
+ // x.getPolicy ().get<0> ().set_max_size (100);
+ // x.getPolicy ().get<1> ().set_max_size (3);
+ // // // x.getPolicy ().get<1> ().set_max_size (3);
+ // // // // x.getPolicy ().get1 ().set_max_size (10);
+ // // // // x.getPolicy ().get2 ().set_max_size (3);
- // // // x.getTrie ().PrintStat (std::cout);
+ // // // // x.getTrie ().PrintStat (std::cout);
- ns3::CcnxNameComponents n1,n2,n3,n4;
- // // // n1("a")("b")("c");
- // // // n2("a")("b")("d");
- // // // n3("a")("b")("f");
- // // // n4("a")("b");
+ // ns3::CcnxNameComponents n1,n2,n3,n4;
+ // // // // n1("a")("b")("c");
+ // // // // n2("a")("b")("d");
+ // // // // n3("a")("b")("f");
+ // // // // n4("a")("b");
- n1("a");
- n2("b");
- n3("c");
- n4("d");
+ // n1("a");
+ // n2("b");
+ // n3("c");
+ // n4("d");
- x.insert (n1, ns3::Create<Integer> (1));
- x.insert (n2, ns3::Create<Integer> (2));
- // // // x.longest_prefix_match (n1);
- x.insert (n3, ns3::Create<Integer> (3));
- x.insert (n4, ns3::Create<Integer> (4));
- x.insert (n4, ns3::Create<Integer> (4));
+ // x.insert (n1, ns3::Create<Integer> (1));
+ // x.insert (n2, ns3::Create<Integer> (2));
+ // // // // x.longest_prefix_match (n1);
+ // x.insert (n3, ns3::Create<Integer> (3));
+ // x.insert (n4, ns3::Create<Integer> (4));
+ // x.insert (n4, ns3::Create<Integer> (4));
- std::cout << "digraph trie {\n";
- std::cout << x.getTrie ();
- std::cout << "}\n";
+ // std::cout << "digraph trie {\n";
+ // std::cout << x.getTrie ();
+ // std::cout << "}\n";
+ Ptr<Node> node = CreateObject<Node> ();
+ Names::Add ("TestNode", node);
+ Ptr<CcnxApp> app = CreateObject<CcnxApp> ();
+ node->AddApplication (app);
+
+ ObjectFactory factory ("ns3::CcnxFib");
+
+ Ptr<CcnxFib> fib = factory.Create<CcnxFib> ();
+ node->AggregateObject (fib);
+ Ptr<CcnxFace> face = CreateObject<CcnxAppFace> (app);
+
+ fib->Add (lexical_cast<CcnxNameComponents> ("/bla"), face, 1);
+ fib->Add (lexical_cast<CcnxNameComponents> ("/bla/1"), face, 1);
+ fib->Add (lexical_cast<CcnxNameComponents> ("/bla/2"), face, 1);
+ fib->Add (lexical_cast<CcnxNameComponents> ("/bla/3"), face, 1);
+ fib->Add (lexical_cast<CcnxNameComponents> ("/bla/1/1"), face, 1);
+ fib->Add (lexical_cast<CcnxNameComponents> ("/bla/1/2"), face, 1);
+
+ cout << *fib << endl;
+
+ fib->RemoveFromAll (face);
+
+ cout << *fib << endl;
// BOOST_FOREACH (const trie::parent_trie &item, x.getPolicy ())
// {
// std::cout << *item.payload () << " " << std::endl;
diff --git a/helper/ccnx-stack-helper.cc b/helper/ccnx-stack-helper.cc
index c7c4908..249954f 100644
--- a/helper/ccnx-stack-helper.cc
+++ b/helper/ccnx-stack-helper.cc
@@ -213,7 +213,8 @@
Ptr<Ccnx> ccnx = m_ccnxFactory.Create<Ccnx> ();
// Create and aggregate FIB
- ccnx->AggregateObject (m_fibFactory.Create<CcnxFib> ());
+ Ptr<CcnxFib> fib = m_fibFactory.Create<CcnxFib> ();
+ ccnx->AggregateObject (fib);
// Create and aggregate PIT
ccnx->AggregateObject (m_pitFactory.Create<CcnxPit> ());
diff --git a/model/ccnx-fib-impl.cc b/model/ccnx-fib-impl.cc
index 18d07ad..ba970fd 100644
--- a/model/ccnx-fib-impl.cc
+++ b/model/ccnx-fib-impl.cc
@@ -91,10 +91,12 @@
CcnxFib::iterator
CcnxFibImpl::Add (const Ptr<const CcnxNameComponents> &prefix, Ptr<CcnxFace> face, int32_t metric)
{
- NS_LOG_FUNCTION(this->GetObject<Node> ()->GetId () << boost::cref(*prefix) << boost::cref(*face) << metric);
+ NS_LOG_FUNCTION (this);
+ // NS_LOG_FUNCTION(this->GetObject<Node> ()->GetId () << boost::cref(*prefix) << boost::cref(*face) << metric);
// will add entry if doesn't exists, or just return an iterator to the existing entry
- std::pair< super::iterator, bool > result = super::insert (*prefix, Create<CcnxFibEntry> (prefix));
+ Ptr<CcnxFibEntry> newEntry = Create<CcnxFibEntry> (prefix);
+ std::pair< super::iterator, bool > result = super::insert (*prefix, newEntry);
NS_ASSERT_MSG (face != NULL, "Trying to modify NULL face");
@@ -112,68 +114,83 @@
super::erase (*prefix);
}
-void
-CcnxFibImpl::Invalidate (const Ptr<const CcnxNameComponents> &prefix)
-{
- NS_LOG_FUNCTION (this->GetObject<Node> ()->GetId () << boost::cref(*prefix));
+// void
+// CcnxFibImpl::Invalidate (const Ptr<const CcnxNameComponents> &prefix)
+// {
+// NS_LOG_FUNCTION (this->GetObject<Node> ()->GetId () << boost::cref(*prefix));
- super::iterator foundItem, lastItem;
- bool reachLast;
- boost::tie (foundItem, reachLast, lastItem) = super::getTrie ().find (*prefix);
+// super::iterator foundItem, lastItem;
+// bool reachLast;
+// boost::tie (foundItem, reachLast, lastItem) = super::getTrie ().find (*prefix);
- if (!reachLast || lastItem->payload () == 0)
- return; // nothing to invalidate
+// if (!reachLast || lastItem->payload () == 0)
+// return; // nothing to invalidate
- super::modify (lastItem,
- ll::bind (&CcnxFibEntry::Invalidate, ll::_1));
-}
+// super::modify (lastItem,
+// ll::bind (&CcnxFibEntry::Invalidate, ll::_1));
+// }
void
CcnxFibImpl::InvalidateAll ()
{
- // NS_LOG_FUNCTION (this->GetObject<Node> ()->GetId ());
+ NS_LOG_FUNCTION (this->GetObject<Node> ()->GetId ());
- // for (super::iterator entry = m_fib.begin ();
- // entry != m_fib.end ();
- // entry ++)
- // {
- // m_fib.modify (entry,
- // ll::bind (&CcnxFibEntry::Invalidate, ll::_1));
- // }
+ super::parent_trie::recursive_iterator item (super::getTrie ());
+ super::parent_trie::recursive_iterator end (0);
+ for (; item != end; item++)
+ {
+ if (item->payload () == 0) continue;
+
+ super::modify (&(*item),
+ ll::bind (&CcnxFibEntry::Invalidate, ll::_1));
+ }
}
void
-CcnxFibImpl::Remove (const CcnxFibEntry &entry, Ptr<CcnxFace> face)
+CcnxFibImpl::Remove (super::parent_trie &item, Ptr<CcnxFace> face)
{
- // NS_LOG_FUNCTION (this);
+ if (item.payload () == 0) return;
+ NS_LOG_FUNCTION (this);
- // m_fib.modify (m_fib.iterator_to (entry),
- // ll::bind (&CcnxFibEntry::RemoveFace, ll::_1, face));
- // if (entry.m_faces.size () == 0)
- // {
- // m_fib.erase (m_fib.iterator_to (entry));
- // }
+ super::modify (&item,
+ ll::bind (&CcnxFibEntry::RemoveFace, ll::_1, face));
}
void
CcnxFibImpl::RemoveFromAll (Ptr<CcnxFace> face)
{
- // NS_LOG_FUNCTION (this);
+ NS_LOG_FUNCTION (this);
- // for_each (m_fib.begin (), m_fib.end (),
- // ll::bind (static_cast< void (CcnxFib::*) (const CcnxFibEntry &, Ptr<CcnxFace>) > (&CcnxFib::Remove),
- // this, ll::_1, face));
+ std::for_each (super::parent_trie::recursive_iterator (super::getTrie ()),
+ super::parent_trie::recursive_iterator (0),
+ ll::bind (static_cast< void (CcnxFib::*) (super::parent_trie &, Ptr<CcnxFace>) > (&CcnxFibImpl::Remove),
+ this, ll::_1, face));
+
+ super::parent_trie::recursive_iterator trieNode (super::getTrie ());
+ super::parent_trie::recursive_iterator end (0);
+ for (; trieNode != end; trieNode++)
+ {
+ if (trieNode->payload () == 0) continue;
+
+ if (trieNode->payload ()->m_faces.size () == 0)
+ {
+ trieNode = super::parent_trie::recursive_iterator (trieNode->erase ());
+ }
+ }
}
void
CcnxFibImpl::Print (std::ostream &os) const
{
- // for (super::iterator entry = fib.m_fib.begin ();
- // entry != fib.m_fib.end ();
- // entry++)
- // {
- // os << entry->GetPrefix () << "\t" << *entry << "\n";
- // }
+ // !!! unordered_set imposes "random" order of item in the same level !!!
+ super::parent_trie::const_recursive_iterator item (super::getTrie ());
+ super::parent_trie::const_recursive_iterator end (0);
+ for (; item != end; item++)
+ {
+ if (item->payload () == 0) continue;
+
+ os << item->payload ()->GetPrefix () << "\t" << *item->payload () << "\n";
+ }
}
} // namespace ns3
diff --git a/model/ccnx-fib-impl.h b/model/ccnx-fib-impl.h
index b10d558..5ef9610 100644
--- a/model/ccnx-fib-impl.h
+++ b/model/ccnx-fib-impl.h
@@ -110,14 +110,14 @@
void
Remove (const Ptr<const CcnxNameComponents> &prefix);
- /**
- * @brief Invalidate FIB entry ("Safe" version of Remove)
- *
- * All faces for the entry will be assigned maximum routing metric and NDN_FIB_RED status
- * @param name Smart pointer to prefix
- */
- void
- Invalidate (const Ptr<const CcnxNameComponents> &prefix);
+ // /**
+ // * @brief Invalidate FIB entry ("Safe" version of Remove)
+ // *
+ // * All faces for the entry will be assigned maximum routing metric and NDN_FIB_RED status
+ // * @param name Smart pointer to prefix
+ // */
+ // void
+ // Invalidate (const Ptr<const CcnxNameComponents> &prefix);
/**
* @brief Invalidate all FIB entries
@@ -126,13 +126,6 @@
InvalidateAll ();
/**
- * @brief Remove reference to a face from the entry. If entry had only this face, the whole
- * entry will be removed
- */
- void
- Remove (const CcnxFibEntry &entry, Ptr<CcnxFace> face);
-
- /**
* @brief Remove all references to a face from FIB. If for some enty that face was the only element,
* this FIB entry will be removed.
*/
@@ -149,13 +142,27 @@
bool
modify (CcnxFib::iterator position, Modifier mod)
{
- return this->modify (position, mod);
+ mod (*position);
+
+ return true;
+ // somehow we need to obtain trie iterator from the payload...
+ // super::getPolicy ().
+ // return super::modify (position, mod);
}
protected:
// inherited from Object class
virtual void NotifyNewAggregate (); ///< @brief Notify when object is aggregated
virtual void DoDispose (); ///< @brief Perform cleanup
+
+private:
+ /**
+ * @brief Remove reference to a face from the entry. If entry had only this face, the whole
+ * entry will be removed
+ */
+ void
+ Remove (super::parent_trie &item, Ptr<CcnxFace> face);
+
private:
Ptr<Node> m_node;
diff --git a/model/ccnx-fib.cc b/model/ccnx-fib.cc
index 5bbbc15..c8153fc 100644
--- a/model/ccnx-fib.cc
+++ b/model/ccnx-fib.cc
@@ -39,6 +39,12 @@
using namespace __ccnx_private;
+TypeId
+CcnxFib::GetTypeId (void)
+{
+ return CcnxFibImpl::GetTypeId ();
+}
+
std::ostream& operator<< (std::ostream& os, const CcnxFib &fib)
{
os << "Node " << Names::FindName (fib.GetObject<Node>()) << "\n";
diff --git a/model/ccnx-fib.h b/model/ccnx-fib.h
index 31fd2d8..4d4c7f7 100644
--- a/model/ccnx-fib.h
+++ b/model/ccnx-fib.h
@@ -41,6 +41,12 @@
typedef ns3::Ptr<CcnxFibEntry> const_iterator;
/**
+ * \brief Interface ID
+ *
+ * \return interface ID
+ */
+ static TypeId GetTypeId ();
+ /**
* @brief Default constructor
*/
CcnxFib () {}
@@ -100,14 +106,14 @@
virtual void
Remove (const Ptr<const CcnxNameComponents> &prefix) = 0;
- /**
- * @brief Invalidate FIB entry ("Safe" version of Remove)
- *
- * All faces for the entry will be assigned maximum routing metric and NDN_FIB_RED status
- * @param name Smart pointer to prefix
- */
- virtual void
- Invalidate (const Ptr<const CcnxNameComponents> &prefix) = 0;
+ // /**
+ // * @brief Invalidate FIB entry ("Safe" version of Remove)
+ // *
+ // * All faces for the entry will be assigned maximum routing metric and NDN_FIB_RED status
+ // * @param name Smart pointer to prefix
+ // */
+ // virtual void
+ // Invalidate (const Ptr<const CcnxNameComponents> &prefix) = 0;
/**
* @brief Invalidate all FIB entries
@@ -116,13 +122,6 @@
InvalidateAll () = 0;
/**
- * @brief Remove reference to a face from the entry. If entry had only this face, the whole
- * entry will be removed
- */
- virtual void
- Remove (const CcnxFibEntry &entry, Ptr<CcnxFace> face) = 0;
-
- /**
* @brief Remove all references to a face from FIB. If for some enty that face was the only element,
* this FIB entry will be removed.
*/
diff --git a/utils/trie-with-policy.h b/utils/trie-with-policy.h
index 79480da..d477643 100644
--- a/utils/trie-with-policy.h
+++ b/utils/trie-with-policy.h
@@ -200,6 +200,9 @@
const parent_trie &
getTrie () const { return trie_; }
+ parent_trie &
+ getTrie () { return trie_; }
+
const policy_container &
getPolicy () const { return policy_; }
diff --git a/utils/trie.h b/utils/trie.h
index 86ca01f..1b2056e 100644
--- a/utils/trie.h
+++ b/utils/trie.h
@@ -30,6 +30,7 @@
#include <boost/interprocess/smart_ptr/unique_ptr.hpp>
#include <boost/tuple/tuple.hpp>
#include <boost/foreach.hpp>
+#include <boost/mpl/if.hpp>
namespace ndnSIM
{
@@ -92,7 +93,8 @@
///////////////////////////////////////////////////
// actual definition
//
-
+template<class T>
+class trie_iterator;
template<typename FullKey,
typename Payload, typename PayloadTraits,
@@ -104,18 +106,52 @@
typedef trie* iterator;
typedef const trie* const_iterator;
+
+ typedef trie_iterator<trie> recursive_iterator;
+ typedef trie_iterator<const trie> const_recursive_iterator;
inline
- trie (const Key &key, size_t bucketSize = 10, size_t bucketIncrement = 10);
+ trie (const Key &key, size_t bucketSize = 10, size_t bucketIncrement = 10)
+ : key_ (key)
+ , initialBucketSize_ (bucketSize)
+ , bucketIncrement_ (bucketIncrement)
+ , bucketSize_ (initialBucketSize_)
+ , buckets_ (new bucket_type [bucketSize_]) //cannot use normal pointer, because lifetime of buckets should be larger than lifetime of the container
+ , children_ (bucket_traits (buckets_.get (), bucketSize_))
+ , payload_ (PayloadTraits::empty_payload)
+ , parent_ (0)
+ {
+ }
inline
- ~trie ();
+ ~trie ()
+ {
+ payload_ = PayloadTraits::empty_payload; // necessary for smart pointers...
+ children_.clear_and_dispose (trie_delete_disposer ());
+ }
void
clear ()
{
children_.clear_and_dispose (trie_delete_disposer ());
}
+
+ template<class Predicate>
+ void
+ clear_if (Predicate cond)
+ {
+ recursive_iterator trieNode (this);
+ recursive_iterator end (0);
+
+ while (trieNode != end)
+ {
+ if (cond (*trieNode))
+ {
+ trieNode = recursive_iterator (trieNode->erase ());
+ }
+ trieNode ++;
+ }
+ }
// actual entry
friend bool
@@ -127,19 +163,73 @@
inline std::pair<iterator, bool>
insert (const FullKey &key,
- typename PayloadTraits::pointer_type payload);
+ typename PayloadTraits::pointer_type payload)
+ {
+ trie *trieNode = this;
+
+ BOOST_FOREACH (const Key &subkey, key)
+ {
+ typename unordered_set::iterator item = trieNode->children_.find (subkey);
+ if (item == trieNode->children_.end ())
+ {
+ trie *newNode = new trie (subkey, initialBucketSize_, bucketIncrement_);
+ // std::cout << "new " << newNode << "\n";
+ newNode->parent_ = trieNode;
+
+ if (trieNode->children_.size () >= trieNode->bucketSize_)
+ {
+ trieNode->bucketSize_ += trieNode->bucketIncrement_;
+ buckets_array newBuckets (new bucket_type [trieNode->bucketSize_]);
+ trieNode->children_.rehash (bucket_traits (newBuckets.get (), trieNode->bucketSize_));
+ trieNode->buckets_.swap (newBuckets);
+ }
+
+ std::pair< typename unordered_set::iterator, bool > ret =
+ trieNode->children_.insert (*newNode);
+
+ trieNode = &(*ret.first);
+ }
+ else
+ trieNode = &(*item);
+ }
+
+ if (trieNode->payload_ == PayloadTraits::empty_payload)
+ {
+ trieNode->payload_ = payload;
+ return std::make_pair (trieNode, true);
+ }
+ else
+ return std::make_pair (trieNode, false);
+ }
/**
* @brief Removes payload (if it exists) and if there are no children, prunes parents trie
*/
- inline void
- erase ();
+ inline iterator
+ erase ()
+ {
+ payload_ = PayloadTraits::empty_payload;
+ return prune ();
+ }
/**
* @brief Do exactly as erase, but without erasing the payload
*/
- inline void
- prune ();
+ inline iterator
+ prune ()
+ {
+ if (payload_ == PayloadTraits::empty_payload &&
+ children_.size () == 0)
+ {
+ if (parent_ == 0) return this;
+
+ trie *parent = parent_;
+ parent->children_.erase_and_dispose (*this, trie_delete_disposer ()); // delete this; basically, committing a suicide
+
+ return parent->prune ();
+ }
+ return this;
+ }
inline boost::tuple<const iterator, bool, const iterator>
find (const FullKey &key) const
@@ -154,14 +244,55 @@
* @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;
+ iterator foundNode = (payload_ != PayloadTraits::empty_payload) ? this : 0;
+ bool reachLast = true;
+
+ BOOST_FOREACH (const Key &subkey, key)
+ {
+ typename unordered_set::iterator item = trieNode->children_.find (subkey);
+ if (item == trieNode->children_.end ())
+ {
+ reachLast = false;
+ break;
+ }
+ else
+ {
+ trieNode = &(*item);
+
+ if (trieNode->payload_ != PayloadTraits::empty_payload)
+ foundNode = trieNode;
+ }
+ }
+
+ return boost::make_tuple (foundNode, reachLast, trieNode);
+ }
/**
* @brief Find next payload of the sub-trie
* @returns end() or a valid iterator pointing to the trie leaf (order is not defined, enumeration )
*/
inline iterator
- find ();
+ find ()
+ {
+ if (payload_ != PayloadTraits::empty_payload)
+ return this;
+
+ typedef trie<FullKey, Payload, PayloadTraits, PolicyHook> trie;
+ for (typename trie::unordered_set::iterator subnode = children_.begin ();
+ subnode != children_.end ();
+ subnode++ )
+ // BOOST_FOREACH (trie &subnode, children_)
+ {
+ iterator value = subnode->find ();
+ if (value != 0)
+ return value;
+ }
+
+ return 0;
+ }
/**
* @brief Find next payload of the sub-trie satisfying the predicate
@@ -170,7 +301,24 @@
*/
template<class Predicate>
inline iterator
- find_if (Predicate pred);
+ find_if (Predicate pred)
+ {
+ if (payload_ != PayloadTraits::empty_payload && pred (payload_))
+ return this;
+
+ typedef trie<FullKey, Payload, 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 (value != 0)
+ return value;
+ }
+
+ return 0;
+ }
iterator end ()
{
@@ -209,7 +357,6 @@
{
void operator() (trie *delete_this)
{
- // std::cout << "Deleting " << delete_this << "\n";
delete delete_this;
}
};
@@ -238,10 +385,14 @@
typedef boost::intrusive::member_hook< trie,
boost::intrusive::unordered_set_member_hook< >,
&trie::unordered_set_member_hook_ > member_hook;
+
typedef boost::intrusive::unordered_set< trie, member_hook > unordered_set;
typedef typename unordered_set::bucket_type bucket_type;
typedef typename unordered_set::bucket_traits bucket_traits;
+ template<class T>
+ friend class trie_iterator;
+
////////////////////////////////////////////////
// Actual data
////////////////////////////////////////////////
@@ -260,173 +411,8 @@
trie *parent_; // to make cleaning effective
};
-template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook>
-trie<FullKey, Payload, PayloadTraits, PolicyHook>
-::trie (const trie::Key &key, size_t bucketSize, size_t bucketIncrement)
- : key_ (key)
- , initialBucketSize_ (bucketSize)
- , bucketIncrement_ (bucketIncrement)
- , bucketSize_ (initialBucketSize_)
- , buckets_ (new bucket_type [bucketSize_]) //cannot use normal pointer, because lifetime of buckets should be larger than lifetime of the container
- , children_ (bucket_traits (buckets_.get (), bucketSize_))
- , payload_ (PayloadTraits::empty_payload)
- , parent_ (0)
-{
-}
-
-template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook>
-trie<FullKey, Payload, PayloadTraits, PolicyHook>
-::~trie ()
-{
- payload_ = PayloadTraits::empty_payload; // necessary for smart pointers...
- children_.clear_and_dispose (trie_delete_disposer ());
-}
-
-template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook>
-inline
-std::pair<typename trie<FullKey, Payload, PayloadTraits, PolicyHook>::iterator, bool>
-trie<FullKey, Payload, PayloadTraits, PolicyHook>
-::insert (const FullKey &key, typename PayloadTraits::pointer_type payload)
-{
- trie *trieNode = this;
-
- BOOST_FOREACH (const Key &subkey, key)
- {
- typename unordered_set::iterator item = trieNode->children_.find (subkey);
- if (item == trieNode->children_.end ())
- {
- trie *newNode = new trie (subkey, initialBucketSize_, bucketIncrement_);
- // std::cout << "new " << newNode << "\n";
- newNode->parent_ = trieNode;
-
- if (trieNode->children_.size () >= trieNode->bucketSize_)
- {
- trieNode->bucketSize_ += trieNode->bucketIncrement_;
- buckets_array newBuckets (new bucket_type [trieNode->bucketSize_]);
- trieNode->children_.rehash (bucket_traits (newBuckets.get (), trieNode->bucketSize_));
- trieNode->buckets_.swap (newBuckets);
- }
-
- std::pair< typename unordered_set::iterator, bool > ret =
- trieNode->children_.insert (*newNode);
-
- trieNode = &(*ret.first);
- }
- else
- trieNode = &(*item);
- }
-
- if (trieNode->payload_ == 0)
- {
- trieNode->payload_ = payload;
- return std::make_pair (trieNode, true);
- }
- else
- return std::make_pair (trieNode, false);
-}
-
-template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook>
-inline
-boost::tuple<typename trie<FullKey, Payload, PayloadTraits, PolicyHook>::iterator,
- bool,
- typename trie<FullKey, Payload, PayloadTraits, PolicyHook>::iterator>
-trie<FullKey, Payload, PayloadTraits, PolicyHook>
-::find (const FullKey &key)
-{
- trie *trieNode = this;
- iterator foundNode = (payload_ != PayloadTraits::empty_payload) ? this : 0;
- bool reachLast = true;
-
- BOOST_FOREACH (const Key &subkey, key)
- {
- typename unordered_set::iterator item = trieNode->children_.find (subkey);
- if (item == trieNode->children_.end ())
- {
- reachLast = false;
- break;
- }
- else
- {
- trieNode = &(*item);
-
- if (trieNode->payload_ != PayloadTraits::empty_payload)
- foundNode = trieNode;
- }
- }
-
- return boost::make_tuple (foundNode, reachLast, trieNode);
-}
-
-template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook>
-inline typename trie<FullKey, Payload, PayloadTraits, PolicyHook>::iterator
-trie<FullKey, Payload, PayloadTraits, PolicyHook>
-::find ()
-{
- if (payload_ != PayloadTraits::empty_payload)
- return this;
-
- typedef trie<FullKey, Payload, PayloadTraits, PolicyHook> trie;
- for (typename trie::unordered_set::iterator subnode = children_.begin ();
- subnode != children_.end ();
- subnode++ )
- // BOOST_FOREACH (trie &subnode, children_)
- {
- iterator value = subnode->find ();
- if (value != 0)
- return value;
- }
-
- return 0;
-}
-
-template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook>
-template<class Predicate>
-inline typename trie<FullKey, Payload, PayloadTraits, PolicyHook>::iterator
-trie<FullKey, Payload, PayloadTraits, PolicyHook>
-::find_if (Predicate pred)
-{
- if (payload_ != PayloadTraits::empty_payload && pred (payload_))
- return this;
-
- typedef trie<FullKey, Payload, PayloadTraits, 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 (value != 0)
- return value;
- }
-
- return 0;
-}
-template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook>
-inline void
-trie<FullKey, Payload, PayloadTraits, PolicyHook>
-::erase ()
-{
- payload_ = PayloadTraits::empty_payload;
- prune ();
-}
-
-template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook>
-inline void
-trie<FullKey, Payload, PayloadTraits, PolicyHook>
-::prune ()
-{
- if (payload_ == 0 && 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
-
- parent->prune ();
- }
-}
template<typename FullKey, typename Payload, typename PayloadTraits, typename PolicyHook>
inline std::ostream&
@@ -490,6 +476,72 @@
return boost::hash_value (trie_node.key_);
}
+
+
+template<class Trie>
+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> &other) const { return (trie_ == other.trie_); }
+ bool operator== (trie_iterator<Trie> &other) { return (trie_ == other.trie_); }
+ bool operator!= (trie_iterator<const Trie> &other) const { return !(*this == other); }
+ bool operator!= (trie_iterator<Trie> &other) { return !(*this == other); }
+
+ trie_iterator<Trie> &
+ operator++ (int)
+ {
+ if (trie_->children_.size () > 0)
+ trie_ = &(*trie_->children_.begin ());
+ else
+ trie_ = goUp ();
+ return *this;
+ }
+
+ trie_iterator<Trie> &
+ operator++ ()
+ {
+ (*this)++;
+ return *this;
+ }
+
+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;
+
+ Trie* goUp ()
+ {
+ if (trie_->parent_ != 0)
+ {
+ // typename Trie::unordered_set::iterator item =
+ set_iterator item = trie_->parent_->children_.iterator_to (*trie_);
+ item++;
+ if (item != trie_->parent_->children_.end ())
+ {
+ return &(*item);
+ }
+ else
+ {
+ trie_ = trie_->parent_;
+ return goUp ();
+ }
+ }
+ else
+ return 0;
+ }
+private:
+ Trie *trie_;
+};
+
+
} // ndnSIM
#endif // TRIE_H_