Adding nsync for NLSR
diff --git a/nsync/src/sync-diff-leaf.cc b/nsync/src/sync-diff-leaf.cc
new file mode 100644
index 0000000..bdbbd1b
--- /dev/null
+++ b/nsync/src/sync-diff-leaf.cc
@@ -0,0 +1,74 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ * Chaoyi Bian <bcy@pku.edu.cn>
+ * Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#include "sync-diff-leaf.h"
+#include <boost/throw_exception.hpp>
+typedef boost::error_info<struct tag_errmsg, std::string> errmsg_info;
+
+using namespace Sync::Error;
+
+namespace Sync {
+
+DiffLeaf::DiffLeaf (NameInfoConstPtr info, const SeqNo &seq)
+ : Leaf (info, seq)
+ , m_op (UPDATE)
+{
+}
+
+DiffLeaf::DiffLeaf (NameInfoConstPtr info)
+ : Leaf (info, SeqNo (0,0))
+ , m_op (REMOVE)
+{
+}
+
+std::ostream &
+operator << (std::ostream &os, Operation op)
+{
+ switch (op)
+ {
+ case UPDATE:
+ os << "update";
+ break;
+ case REMOVE:
+ os << "remove";
+ break;
+ }
+ return os;
+}
+
+std::istream &
+operator >> (std::istream &is, Operation &op)
+{
+ std::string operation;
+ is >> operation;
+ if (operation == "update")
+ op = UPDATE;
+ else if (operation == "remove")
+ op = REMOVE;
+ else
+ BOOST_THROW_EXCEPTION (SyncDiffLeafOperationParseError () << errmsg_info (operation));
+
+ return is;
+}
+
+
+}
diff --git a/nsync/src/sync-diff-leaf.h b/nsync/src/sync-diff-leaf.h
new file mode 100644
index 0000000..6e09efe
--- /dev/null
+++ b/nsync/src/sync-diff-leaf.h
@@ -0,0 +1,91 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ * Chaoyi Bian <bcy@pku.edu.cn>
+ * Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef SYNC_DIFF_LEAF_H
+#define SYNC_DIFF_LEAF_H
+
+#include "sync-leaf.h"
+#include <boost/exception/all.hpp>
+
+namespace Sync {
+
+/**
+ * @ingroup sync
+ * @brief Annotation for SYNC leaf
+ */
+enum Operation
+ {
+ UPDATE, ///< @brief Leaf was added or updated
+ REMOVE ///< @brief Leaf was removed
+ };
+
+/**
+ * @ingroup sync
+ * @brief Annotated SYNC leaf
+ */
+class DiffLeaf : public Leaf
+{
+public:
+ /**
+ * @brief Constructor to create an UPDATE diff leaf
+ * @param info Smart pointer to leaf's name
+ * @param seq Initial sequence number of the pointer
+ */
+ DiffLeaf (NameInfoConstPtr info, const SeqNo &seq);
+
+ /**
+ * @brief Constructor to create an REMOVE diff leaf
+ * @param info Smart pointer to leaf's name
+ *
+ * This constructor creates a leaf with phony sequence number
+ * with 0 session ID and 0 sequence number
+ */
+ DiffLeaf (NameInfoConstPtr info);
+
+ virtual ~DiffLeaf () { }
+
+ /**
+ * @brief Get diff leaf type
+ */
+ Operation
+ getOperation () const { return m_op; }
+
+private:
+ Operation m_op;
+};
+
+typedef boost::shared_ptr<DiffLeaf> DiffLeafPtr;
+typedef boost::shared_ptr<const DiffLeaf> DiffLeafConstPtr;
+
+std::ostream &
+operator << (std::ostream &os, Operation op);
+
+std::istream &
+operator >> (std::istream &is, Operation &op);
+
+namespace Error {
+struct SyncDiffLeafOperationParseError : virtual boost::exception, virtual std::exception { };
+} // Error
+
+} // Sync
+
+#endif // SYNC_DIFF_LEAF_H
diff --git a/nsync/src/sync-diff-state-container.h b/nsync/src/sync-diff-state-container.h
new file mode 100644
index 0000000..2ae7c59
--- /dev/null
+++ b/nsync/src/sync-diff-state-container.h
@@ -0,0 +1,72 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ * Chaoyi Bian <bcy@pku.edu.cn>
+ * Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef SYNC_DIFF_STATE_CONTAINER_H
+#define SYNC_DIFF_STATE_CONTAINER_H
+
+#include "sync-diff-state.h"
+#include "sync-digest.h"
+
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/tag.hpp>
+// #include <boost/multi_index/ordered_index.hpp>
+// #include <boost/multi_index/composite_key.hpp>
+#include <boost/multi_index/hashed_index.hpp>
+#include <boost/multi_index/sequenced_index.hpp>
+// #include <boost/multi_index/random_access_index.hpp>
+#include <boost/multi_index/member.hpp>
+#include <boost/multi_index/mem_fun.hpp>
+
+namespace mi = boost::multi_index;
+
+namespace Sync {
+
+/// @cond include_hidden
+struct sequenced { };
+struct timed { };
+/// @endcond
+
+/**
+ * \ingroup sync
+ * @brief Container for differential states
+ */
+struct DiffStateContainer : public mi::multi_index_container<
+ DiffStatePtr,
+ mi::indexed_by<
+ // For fast access to elements using DiffState hashes
+ mi::hashed_unique<
+ mi::tag<hashed>,
+ mi::const_mem_fun<DiffState, DigestConstPtr, &DiffState::getDigest>,
+ DigestPtrHash,
+ DigestPtrEqual
+ >
+ ,
+ // sequenced index to access older/newer element (like in list)
+ mi::sequenced<mi::tag<sequenced> >
+ >
+ >
+{
+};
+
+} // Sync
+
+#endif // SYNC_DIFF_STATE_CONTAINER_H
diff --git a/nsync/src/sync-diff-state.cc b/nsync/src/sync-diff-state.cc
new file mode 100644
index 0000000..3030940
--- /dev/null
+++ b/nsync/src/sync-diff-state.cc
@@ -0,0 +1,101 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ * Chaoyi Bian <bcy@pku.edu.cn>
+ * Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#include "sync-diff-state.h"
+#include "sync-diff-leaf.h"
+
+#include <boost/make_shared.hpp>
+#include <boost/foreach.hpp>
+#include <boost/assert.hpp>
+
+using namespace boost;
+
+namespace Sync {
+
+DiffState::DiffState ()
+{
+}
+
+DiffState::~DiffState ()
+{
+}
+
+DiffStatePtr
+DiffState::diff () const
+{
+ DiffStatePtr ret = make_shared<DiffState> ();
+
+ DiffStatePtr state = m_next;
+ while (state != 0)
+ {
+ *ret += *state;
+ state = state->m_next;
+ }
+
+ return ret;
+}
+
+DiffState &
+DiffState::operator += (const DiffState &state)
+{
+ BOOST_FOREACH (LeafConstPtr _leaf, state.getLeaves ())
+ {
+ DiffLeafConstPtr leaf = dynamic_pointer_cast<const DiffLeaf> (_leaf);
+ BOOST_ASSERT (leaf != 0);
+
+ if (leaf->getOperation () == UPDATE)
+ update (leaf->getInfo (), leaf->getSeq ());
+ else if (leaf->getOperation () == REMOVE)
+ remove (leaf->getInfo ());
+ else
+ {
+ BOOST_ASSERT (false);
+ }
+ }
+
+ return *this;
+}
+
+// from State
+boost::tuple<bool/*inserted*/, bool/*updated*/, SeqNo/*oldSeqNo*/>
+DiffState::update (NameInfoConstPtr info, const SeqNo &seq)
+{
+ m_leaves.erase (info);
+
+ DiffLeafPtr leaf = make_shared<DiffLeaf> (info, cref (seq));
+ m_leaves.insert (leaf);
+
+ return make_tuple (true, false, SeqNo ());
+}
+
+bool
+DiffState::remove (NameInfoConstPtr info)
+{
+ m_leaves.erase (info);
+
+ DiffLeafPtr leaf = make_shared<DiffLeaf> (info);
+ m_leaves.insert (leaf);
+
+ return true;
+}
+
+} // ns3
diff --git a/nsync/src/sync-diff-state.h b/nsync/src/sync-diff-state.h
new file mode 100644
index 0000000..d944c3e
--- /dev/null
+++ b/nsync/src/sync-diff-state.h
@@ -0,0 +1,102 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ * Chaoyi Bian <bcy@pku.edu.cn>
+ * Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef SYNC_DIFF_STATE_H
+#define SYNC_DIFF_STATE_H
+
+#include "sync-state.h"
+#include <iostream>
+
+namespace Sync {
+
+class DiffState;
+typedef boost::shared_ptr<DiffState> DiffStatePtr;
+typedef boost::shared_ptr<DiffState> DiffStateConstPtr;
+
+/**
+ * @ingroup ccnx
+ * @brief Differential SYNC state
+ */
+class DiffState : public State
+{
+public:
+ /**
+ * @see Default constructor
+ */
+ DiffState ();
+ virtual ~DiffState ();
+
+ /**
+ * @brief Set successor for the diff state
+ * @param next successor state
+ */
+ void
+ setNext (DiffStatePtr next)
+ {
+ m_next = next;
+ }
+
+ /**
+ * @brief Set digest for the diff state (obtained from a corresponding full state)
+ * @param digest A read only smart pointer to a digest object (that should be unmodified anywhere else)
+ */
+ void
+ setDigest (DigestConstPtr digest) { m_digest = digest; }
+
+ /**
+ * @brief Get digest for the diff state
+ */
+ DigestConstPtr
+ getDigest () const { return m_digest; }
+
+ /**
+ * @brief Accumulate differences from `this' state to the most current state
+ * @returns Accumulated differences from `this' state to the most current state
+ */
+ DiffStatePtr
+ diff () const;
+
+ /**
+ * @brief Combine differences from `this' and `state'
+ * @param state Differential state to combine with
+ * @return Combined differences
+ *
+ * In case of collisions, `this' leaf will be replaced with the leaf of `state'
+ */
+ DiffState&
+ operator += (const DiffState &state);
+
+ // from State
+ virtual boost::tuple<bool/*inserted*/, bool/*updated*/, SeqNo/*oldSeqNo*/>
+ update (NameInfoConstPtr info, const SeqNo &seq);
+
+ virtual bool
+ remove (NameInfoConstPtr info);
+
+private:
+ DiffStatePtr m_next;
+ DigestConstPtr m_digest;
+};
+
+} // Sync
+
+#endif // SYNC_DIFF_STATE_H
diff --git a/nsync/src/sync-digest.cc b/nsync/src/sync-digest.cc
new file mode 100644
index 0000000..6f41d3d
--- /dev/null
+++ b/nsync/src/sync-digest.cc
@@ -0,0 +1,265 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ * Chaoyi Bian <bcy@pku.edu.cn>
+ * Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#include "sync-digest.h"
+#include <string.h>
+
+#include <boost/assert.hpp>
+#include <boost/throw_exception.hpp>
+typedef boost::error_info<struct tag_errmsg, std::string> errmsg_info_str;
+typedef boost::error_info<struct tag_errmsg, int> errmsg_info_int;
+
+// for printing, may be disabled in optimized build
+
+// #ifdef DIGEST_BASE64
+// #include <boost/archive/iterators/base64_from_binary.hpp>
+// #include <boost/archive/iterators/binary_from_base64.hpp>
+// #endif
+
+#include <boost/archive/iterators/transform_width.hpp>
+#include <boost/iterator/transform_iterator.hpp>
+#include <boost/archive/iterators/dataflow_exception.hpp>
+
+using namespace boost;
+using namespace boost::archive::iterators;
+using namespace std;
+
+// Other options: VP_md2, EVP_md5, EVP_sha, EVP_sha1, EVP_sha256, EVP_dss, EVP_dss1, EVP_mdc2, EVP_ripemd160
+#define HASH_FUNCTION EVP_sha256
+#define HASH_FUNCTION_LEN 32
+
+
+// #ifndef DIGEST_BASE64
+
+template<class CharType>
+struct hex_from_4_bit
+{
+ typedef CharType result_type;
+ CharType operator () (CharType ch) const
+ {
+ const char *lookup_table = "0123456789abcdef";
+ // cout << "New character: " << (int) ch << " (" << (char) ch << ")" << "\n";
+ BOOST_ASSERT (ch < 16);
+ return lookup_table[static_cast<size_t>(ch)];
+ }
+};
+
+typedef transform_iterator<hex_from_4_bit<std::vector<uint8_t>::const_iterator::value_type>,
+ transform_width<std::vector<uint8_t>::const_iterator, 4, 8, std::vector<uint8_t>::const_iterator::value_type> > string_from_binary;
+
+
+template<class CharType>
+struct hex_to_4_bit
+{
+ typedef CharType result_type;
+ CharType operator () (CharType ch) const
+ {
+ const signed char lookup_table [] = {
+ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
+ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
+ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
+ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,-1,-1,-1,-1,-1,-1,
+ -1,10,11,12,13,14,15,-1,-1,-1,-1,-1,-1,-1,-1,-1,
+ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
+ -1,10,11,12,13,14,15,-1,-1,-1,-1,-1,-1,-1,-1,-1,
+ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1
+ };
+
+ // cout << "New character: " << hex << (int) ch << " (" << (char) ch << ")" << "\n";
+ signed char value = -1;
+ if ((unsigned)ch < 128)
+ value = lookup_table [(unsigned)ch];
+ if (value == -1)
+ BOOST_THROW_EXCEPTION (Sync::Error::DigestCalculationError () << errmsg_info_int ((int)ch));
+
+ return value;
+ }
+};
+
+typedef transform_width<transform_iterator<hex_to_4_bit<string::const_iterator::value_type>, string::const_iterator>, 8, 4> string_to_binary;
+
+namespace Sync {
+
+Digest::Digest ()
+{
+ m_context = EVP_MD_CTX_create ();
+
+ reset ();
+}
+
+Digest::~Digest ()
+{
+ EVP_MD_CTX_destroy (m_context);
+}
+
+bool
+Digest::empty () const
+{
+ return m_buffer.empty ();
+}
+
+bool
+Digest::isZero () const
+{
+ if (m_buffer.empty ())
+ BOOST_THROW_EXCEPTION (Error::DigestCalculationError ()
+ << errmsg_info_str ("Digest has not been yet finalized"));
+
+ return (m_buffer.size () == 1 && m_buffer[0] == 0);
+}
+
+
+void
+Digest::reset ()
+{
+ m_buffer.clear ();
+
+ int ok = EVP_DigestInit_ex (m_context, HASH_FUNCTION (), 0);
+ if (!ok)
+ BOOST_THROW_EXCEPTION (Error::DigestCalculationError ()
+ << errmsg_info_str ("EVP_DigestInit_ex returned error")
+ << errmsg_info_int (ok));
+}
+
+
+void
+Digest::finalize ()
+{
+ if (!m_buffer.empty ()) return;
+
+ m_buffer.resize (HASH_FUNCTION_LEN);
+
+ unsigned int tmp;
+ int ok = EVP_DigestFinal_ex (m_context,
+ &m_buffer[0], &tmp);
+ if (!ok)
+ BOOST_THROW_EXCEPTION (Error::DigestCalculationError ()
+ << errmsg_info_str ("EVP_DigestFinal_ex returned error")
+ << errmsg_info_int (ok));
+}
+
+std::size_t
+Digest::getHash () const
+{
+ if (isZero ()) return 0;
+
+ if (sizeof (std::size_t) > m_buffer.size ())
+ {
+ BOOST_THROW_EXCEPTION (Error::DigestCalculationError ()
+ << errmsg_info_str ("Hash is not zero and length is less than size_t")
+ << errmsg_info_int (m_buffer.size ()));
+ }
+
+ // just getting first sizeof(std::size_t) bytes
+ // not ideal, but should work pretty well
+ return *(reinterpret_cast<const std::size_t*> (&m_buffer[0]));
+}
+
+bool
+Digest::operator == (const Digest &digest) const
+{
+ if (m_buffer.empty ())
+ BOOST_THROW_EXCEPTION (Error::DigestCalculationError ()
+ << errmsg_info_str ("Digest1 is empty"));
+
+ if (digest.m_buffer.empty ())
+ BOOST_THROW_EXCEPTION (Error::DigestCalculationError ()
+ << errmsg_info_str ("Digest2 is empty"));
+
+ return m_buffer == digest.m_buffer;
+}
+
+
+void
+Digest::update (const uint8_t *buffer, size_t size)
+{
+ // cout << "Update: " << (void*)buffer << " / size: " << size << "\n";
+
+ // cannot update Digest when it has been finalized
+ if (!m_buffer.empty ())
+ BOOST_THROW_EXCEPTION (Error::DigestCalculationError ()
+ << errmsg_info_str ("Digest has been already finalized"));
+
+ bool ok = EVP_DigestUpdate (m_context, buffer, size);
+ if (!ok)
+ BOOST_THROW_EXCEPTION (Error::DigestCalculationError ()
+ << errmsg_info_str ("EVP_DigestUpdate returned error")
+ << errmsg_info_int (ok));
+}
+
+
+Digest &
+Digest::operator << (const Digest &src)
+{
+ if (src.m_buffer.empty ())
+ BOOST_THROW_EXCEPTION (Error::DigestCalculationError ()
+ << errmsg_info_str ("Digest has not been yet finalized"));
+
+ update (&src.m_buffer[0], src.m_buffer.size ());
+
+ return *this;
+}
+
+std::ostream &
+operator << (std::ostream &os, const Digest &digest)
+{
+ BOOST_ASSERT (!digest.m_buffer.empty ());
+
+ ostreambuf_iterator<char> out_it (os); // ostream iterator
+ // need to encode to base64
+ copy (string_from_binary (digest.m_buffer.begin ()),
+ string_from_binary (digest.m_buffer.end ()),
+ out_it);
+
+ return os;
+}
+
+std::istream &
+operator >> (std::istream &is, Digest &digest)
+{
+ string str;
+ is >> str; // read string first
+
+ if (str.size () == 0)
+ BOOST_THROW_EXCEPTION (Error::DigestCalculationError ()
+ << errmsg_info_str ("Input is empty"));
+
+ // uint8_t padding = (3 - str.size () % 3) % 3;
+ // for (uint8_t i = 0; i < padding; i++) str.push_back ('=');
+
+ // only empty digest object can be used for reading
+ if (!digest.m_buffer.empty ())
+ BOOST_THROW_EXCEPTION (Error::DigestCalculationError ()
+ << errmsg_info_str ("Digest has been already finalized"));
+
+ digest.m_buffer.clear ();
+
+ copy (string_to_binary (str.begin ()),
+ string_to_binary (str.end ()),
+ std::back_inserter (digest.m_buffer));
+
+ return is;
+}
+
+
+} // Sync
+
diff --git a/nsync/src/sync-digest.h b/nsync/src/sync-digest.h
new file mode 100644
index 0000000..ecc8522
--- /dev/null
+++ b/nsync/src/sync-digest.h
@@ -0,0 +1,199 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ * Chaoyi Bian <bcy@pku.edu.cn>
+ * Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef SYNC_DIGEST_H
+#define SYNC_DIGEST_H
+
+#include <boost/exception/all.hpp>
+#include <openssl/evp.h>
+#include <boost/cstdint.hpp>
+#include <vector>
+
+namespace Sync {
+
+/**
+ * @ingroup sync
+ * @brief A simple wrapper for libcrypto hash functions
+ */
+class Digest
+{
+public:
+ /**
+ * @brief Default constructor. Will initialize internal libssl structures
+ */
+ Digest ();
+
+ /**
+ * @brief Check if digest is empty
+ */
+ bool
+ empty () const;
+
+ /**
+ * @brief Reset digest to the initial state
+ */
+ void
+ reset ();
+
+ /**
+ * @brief Destructor
+ */
+ ~Digest ();
+
+ /**
+ * @brief Obtain a short version of the hash (just first sizeof(size_t) bytes
+ *
+ * Side effect: finalize() will be called on `this'
+ */
+ std::size_t
+ getHash () const;
+
+ /**
+ * @brief Finalize digest. All subsequent calls to "operator <<" will fire an exception
+ */
+ void
+ finalize ();
+
+ /**
+ * @brief Compare two full digests
+ *
+ * Side effect: Finalize will be called on `this' and `digest'
+ */
+ bool
+ operator == (const Digest &digest) const;
+
+ bool
+ operator != (const Digest &digest) const
+ { return ! (*this == digest); }
+
+
+ /**
+ * @brief Add existing digest to digest calculation
+ * @param src digest to combine with
+ *
+ * The result of this combination is hash (hash (...))
+ */
+ Digest &
+ operator << (const Digest &src);
+
+ /**
+ * @brief Add string to digest calculation
+ * @param str string to put into digest
+ */
+ inline Digest &
+ operator << (const std::string &str);
+
+ /**
+ * @brief Add uint64_t value to digest calculation
+ * @param value uint64_t value to put into digest
+ */
+ inline Digest &
+ operator << (uint64_t value);
+
+ /**
+ * @brief Checks if the stored hash is zero-root hash
+ *
+ * Zero-root hash is a valid hash that optimally represents an empty state
+ */
+ bool
+ isZero () const;
+
+private:
+ Digest &
+ operator = (Digest &digest) { (void)digest; return *this; }
+
+ /**
+ * @brief Add size bytes of buffer to the hash
+ */
+ void
+ update (const uint8_t *buffer, size_t size);
+
+ friend std::ostream &
+ operator << (std::ostream &os, const Digest &digest);
+
+ friend std::istream &
+ operator >> (std::istream &is, Digest &digest);
+
+private:
+ EVP_MD_CTX *m_context;
+ std::vector<uint8_t> m_buffer;
+};
+
+namespace Error {
+struct DigestCalculationError : virtual boost::exception, virtual std::exception { };
+}
+
+typedef boost::shared_ptr<Digest> DigestPtr;
+typedef boost::shared_ptr<const Digest> DigestConstPtr;
+
+Digest &
+Digest::operator << (const std::string &str)
+{
+ update (reinterpret_cast<const uint8_t*> (str.c_str ()), str.size ());
+ return *this;
+}
+
+inline Digest &
+Digest::operator << (uint64_t value)
+{
+ update (reinterpret_cast<const uint8_t*> (&value), sizeof (uint64_t));
+ return *this;
+}
+
+std::ostream &
+operator << (std::ostream &os, const Digest &digest);
+
+std::istream &
+operator >> (std::istream &is, Digest &digest);
+
+// template<class INT>
+// Digest &
+// Digest::operator << (INT value)
+// {
+// update (&value, sizeof (INT));
+// return *this;
+// }
+
+struct DigestPtrHash : public std::unary_function<Digest, std::size_t>
+{
+ std::size_t
+ operator() (DigestConstPtr digest) const
+ {
+ // std::cout << "digest->getHash: " << digest->getHash () << " (" << *digest << ")" << std::endl;
+ return digest->getHash ();
+ }
+};
+
+struct DigestPtrEqual : public std::unary_function<Digest, std::size_t>
+{
+ bool
+ operator() (DigestConstPtr digest1, DigestConstPtr digest2) const
+ {
+ // std::cout << boost::cref(*digest1) << " == " << boost::cref(*digest2) << " : " << (*digest1 == *digest2) << std::endl;
+ return *digest1 == *digest2;
+ }
+};
+
+
+} // Sync
+
+#endif // SYNC_DIGEST_H
diff --git a/nsync/src/sync-event.h b/nsync/src/sync-event.h
new file mode 100644
index 0000000..7808947
--- /dev/null
+++ b/nsync/src/sync-event.h
@@ -0,0 +1,35 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ * Chaoyi Bian <bcy@pku.edu.cn>
+ * Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef SYNC_EVENT_H
+#define SYNC_EVENT_H
+
+#include <boost/function.hpp>
+
+namespace Sync
+{
+
+typedef boost::function< void ( ) > Event;
+
+} // Sync
+
+#endif // SYNC_EVENT_H
diff --git a/nsync/src/sync-full-leaf.cc b/nsync/src/sync-full-leaf.cc
new file mode 100644
index 0000000..84f96e3
--- /dev/null
+++ b/nsync/src/sync-full-leaf.cc
@@ -0,0 +1,52 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ * Chaoyi Bian <bcy@pku.edu.cn>
+ * Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#include "sync-full-leaf.h"
+#include <boost/ref.hpp>
+
+using namespace boost;
+
+namespace Sync {
+
+FullLeaf::FullLeaf (NameInfoConstPtr info, const SeqNo &seq)
+ : Leaf (info, seq)
+{
+ updateDigest ();
+}
+
+void
+FullLeaf::updateDigest ()
+{
+ m_digest.reset ();
+ m_digest << getInfo ()->getDigest () << *getSeq ().getDigest ();
+ m_digest.finalize ();
+}
+
+// from Leaf
+void
+FullLeaf::setSeq (const SeqNo &seq)
+{
+ Leaf::setSeq (seq);
+ updateDigest ();
+}
+
+} // Sync
diff --git a/nsync/src/sync-full-leaf.h b/nsync/src/sync-full-leaf.h
new file mode 100644
index 0000000..08142a6
--- /dev/null
+++ b/nsync/src/sync-full-leaf.h
@@ -0,0 +1,71 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ * Chaoyi Bian <bcy@pku.edu.cn>
+ * Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef SYNC_FULL_LEAF_H
+#define SYNC_FULL_LEAF_H
+
+#include "sync-leaf.h"
+
+namespace Sync {
+
+/**
+ * @ingroup sync
+ * @brief SYNC leaf for the full state (with support of Digest calculation)
+ */
+class FullLeaf : public Leaf
+{
+public:
+ /**
+ * @brief Constructor to create an UPDATE diff leaf
+ * @param info Smart pointer to leaf's name
+ * @param seq Initial sequence number of the pointer
+ */
+ FullLeaf (NameInfoConstPtr info, const SeqNo &seq);
+ virtual ~FullLeaf () { }
+
+ /**
+ * @brief Get hash digest of the leaf
+ *
+ * The underlying Digest object is recalculated on every update or removal
+ * (including updates of child classes)
+ */
+ const Digest &
+ getDigest () const { return m_digest; }
+
+ // from Leaf
+ virtual void
+ setSeq (const SeqNo &seq);
+
+private:
+ void
+ updateDigest ();
+
+private:
+ Digest m_digest;
+};
+
+typedef boost::shared_ptr<FullLeaf> FullLeafPtr;
+typedef boost::shared_ptr<const FullLeaf> FullLeafConstPtr;
+
+} // Sync
+
+#endif // SYNC_FULL_LEAF_H
diff --git a/nsync/src/sync-full-state.cc b/nsync/src/sync-full-state.cc
new file mode 100644
index 0000000..eb9ca4c
--- /dev/null
+++ b/nsync/src/sync-full-state.cc
@@ -0,0 +1,126 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ * Chaoyi Bian <bcy@pku.edu.cn>
+ * Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#include "sync-full-state.h"
+
+#include <boost/make_shared.hpp>
+#include <boost/lambda/lambda.hpp>
+#include <boost/lambda/bind.hpp>
+#include <boost/foreach.hpp>
+#include <boost/assert.hpp>
+
+#include "sync-full-leaf.h"
+
+using namespace boost;
+namespace ll = boost::lambda;
+
+namespace Sync {
+
+
+FullState::FullState ()
+// m_lastUpdated is initialized to "not_a_date_time" in normal lib mode and to "0" time in NS-3 mode
+{
+}
+
+FullState::~FullState ()
+{
+}
+
+ndn::time::Duration
+FullState::getTimeFromLastUpdate () const
+{
+ return ndn::time::now() - m_lastUpdated;
+}
+
+DigestConstPtr
+FullState::getDigest ()
+{
+ if (!m_digest)
+ {
+ m_digest = make_shared<Digest> ();
+ if (m_leaves.get<ordered> ().size () > 0)
+ {
+ BOOST_FOREACH (LeafConstPtr leaf, m_leaves.get<ordered> ())
+ {
+ FullLeafConstPtr fullLeaf = dynamic_pointer_cast<const FullLeaf> (leaf);
+ BOOST_ASSERT (fullLeaf != 0);
+ *m_digest << fullLeaf->getDigest ();
+ }
+ m_digest->finalize ();
+ }
+ else
+ {
+ std::istringstream is ("00"); //zero state
+ is >> *m_digest;
+ }
+ }
+
+ return m_digest;
+}
+
+// from State
+boost::tuple<bool/*inserted*/, bool/*updated*/, SeqNo/*oldSeqNo*/>
+FullState::update (NameInfoConstPtr info, const SeqNo &seq)
+{
+ m_lastUpdated = ndn::time::now();
+
+
+ m_digest.reset ();
+
+ LeafContainer::iterator item = m_leaves.find (info);
+ if (item == m_leaves.end ())
+ {
+ m_leaves.insert (make_shared<FullLeaf> (info, cref (seq)));
+ return make_tuple (true, false, SeqNo ());
+ }
+ else
+ {
+ if ((*item)->getSeq () == seq || seq < (*item)->getSeq ())
+ {
+ return make_tuple (false, false, SeqNo ());
+ }
+
+ SeqNo old = (*item)->getSeq ();
+ m_leaves.modify (item,
+ ll::bind (&Leaf::setSeq, *ll::_1, seq));
+ return make_tuple (false, true, old);
+ }
+}
+
+bool
+FullState::remove (NameInfoConstPtr info)
+{
+ m_lastUpdated = ndn::time::now();
+
+ m_digest.reset ();
+
+ LeafContainer::iterator item = m_leaves.find (info);
+ if (item != m_leaves.end ())
+ {
+ m_leaves.erase (item);
+ return true;
+ }
+ else
+ return false;
+}
+
+} // Sync
diff --git a/nsync/src/sync-full-state.h b/nsync/src/sync-full-state.h
new file mode 100644
index 0000000..28e0078
--- /dev/null
+++ b/nsync/src/sync-full-state.h
@@ -0,0 +1,79 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ * Chaoyi Bian <bcy@pku.edu.cn>
+ * Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef SYNC_FULL_STATE_H
+#define SYNC_FULL_STATE_H
+
+#include <ndn-cpp-dev/util/time.hpp>
+#include "sync-state.h"
+
+namespace Sync {
+
+class FullState;
+typedef boost::shared_ptr<FullState> FullStatePtr;
+typedef boost::shared_ptr<FullState> FullStateConstPtr;
+
+
+/**
+ * \ingroup sync
+ * @brief Cumulative SYNC state
+ */
+class FullState : public State
+{
+public:
+ /**
+ * @brief Default constructor
+ */
+ FullState ();
+ virtual ~FullState ();
+
+ /**
+ * @brief Get time period since last state update
+ *
+ * This value can be used to randomize reconciliation waiting time in SyncApp
+ */
+ ndn::time::Duration
+ getTimeFromLastUpdate () const;
+
+ /**
+ * @brief Obtain a read-only copy of the digest
+ *
+ * If m_digest is 0, then it is automatically created. On every update and removal, m_digest is reset to 0
+ */
+ DigestConstPtr
+ getDigest ();
+
+ // from State
+ virtual boost::tuple<bool/*inserted*/, bool/*updated*/, SeqNo/*oldSeqNo*/>
+ update (NameInfoConstPtr info, const SeqNo &seq);
+
+ virtual bool
+ remove (NameInfoConstPtr info);
+
+private:
+ ndn::time::Point m_lastUpdated; ///< @brief Time when state was updated last time
+ DigestPtr m_digest;
+};
+
+} // Sync
+
+#endif // SYNC_STATE_H
diff --git a/nsync/src/sync-interest-container.h b/nsync/src/sync-interest-container.h
new file mode 100644
index 0000000..742f053
--- /dev/null
+++ b/nsync/src/sync-interest-container.h
@@ -0,0 +1,99 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ * Chaoyi Bian <bcy@pku.edu.cn>
+ * Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef SYNC_INTEREST_CONTAINER_H
+#define SYNC_INTEREST_CONTAINER_H
+
+#include <ndn-cpp-dev/util/time.hpp>
+
+#include "sync-digest.h"
+
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/tag.hpp>
+// #include <boost/multi_index/ordered_index.hpp>
+// #include <boost/multi_index/composite_key.hpp>
+#include <boost/multi_index/hashed_index.hpp>
+#include <boost/multi_index/sequenced_index.hpp>
+#include <boost/multi_index/ordered_index.hpp>
+// #include <boost/multi_index/random_access_index.hpp>
+#include <boost/multi_index/member.hpp>
+#include <boost/multi_index/mem_fun.hpp>
+
+namespace mi = boost::multi_index;
+
+namespace Sync {
+
+struct Interest
+{
+ Interest (DigestConstPtr digest, const std::string &name, bool unknown=false)
+ : m_digest (digest)
+ , m_name (name)
+ , m_time (ndn::time::now())
+ , m_unknown (unknown)
+ {
+ }
+
+ DigestConstPtr m_digest;
+ std::string m_name;
+ ndn::time::Point m_time;
+ bool m_unknown;
+};
+
+/// @cond include_hidden
+struct named { };
+struct hashed;
+struct timed;
+/// @endcond
+
+/**
+ * \ingroup sync
+ * @brief Container for interests (application PIT)
+ */
+struct InterestContainer : public mi::multi_index_container<
+ Interest,
+ mi::indexed_by<
+ mi::hashed_unique<
+ mi::tag<named>,
+ BOOST_MULTI_INDEX_MEMBER(Interest, std::string, m_name)
+ >
+ ,
+
+ mi::hashed_non_unique<
+ mi::tag<hashed>,
+ BOOST_MULTI_INDEX_MEMBER(Interest, DigestConstPtr, m_digest),
+ DigestPtrHash,
+ DigestPtrEqual
+ >
+ ,
+
+ mi::ordered_non_unique<
+ mi::tag<timed>,
+ BOOST_MULTI_INDEX_MEMBER(Interest, ndn::time::Point, m_time)
+ >
+ >
+ >
+{
+};
+
+} // Sync
+
+#endif // SYNC_INTEREST_CONTAINER_H
diff --git a/nsync/src/sync-interest-table.cc b/nsync/src/sync-interest-table.cc
new file mode 100644
index 0000000..a378950
--- /dev/null
+++ b/nsync/src/sync-interest-table.cc
@@ -0,0 +1,123 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ * Chaoyi Bian <bcy@pku.edu.cn>
+ * Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#include "sync-interest-table.h"
+#include "sync-logging.h"
+using namespace std;
+
+INIT_LOGGER ("SyncInterestTable");
+
+namespace Sync
+{
+
+SyncInterestTable::SyncInterestTable (boost::asio::io_service& io, ndn::time::Duration lifetime)
+ : m_entryLifetime (lifetime)
+ , m_scheduler(io)
+{
+ m_scheduler.schedulePeriodicEvent (ndn::time::seconds (4), ndn::time::seconds (4),
+ ndn::bind(&SyncInterestTable::expireInterests, this));
+}
+
+SyncInterestTable::~SyncInterestTable ()
+{
+}
+
+Interest
+SyncInterestTable::pop ()
+{
+ if (m_table.size () == 0)
+ BOOST_THROW_EXCEPTION (Error::InterestTableIsEmpty ());
+
+ Interest ret = *m_table.begin ();
+ m_table.erase (m_table.begin ());
+
+ return ret;
+}
+
+bool
+SyncInterestTable::insert (DigestConstPtr digest, const string &name, bool unknownState/*=false*/)
+{
+ bool existent = false;
+
+ InterestContainer::index<named>::type::iterator it = m_table.get<named> ().find (name);
+ if (it != m_table.end())
+ {
+ existent = true;
+ m_table.erase (it);
+ }
+ m_table.insert (Interest (digest, name, unknownState));
+
+ return existent;
+}
+
+uint32_t
+SyncInterestTable::size () const
+{
+ return m_table.size ();
+}
+
+bool
+SyncInterestTable::remove (const string &name)
+{
+ InterestContainer::index<named>::type::iterator item = m_table.get<named> ().find (name);
+ if (item != m_table.get<named> ().end ())
+ {
+ m_table.get<named> ().erase (name);
+ return true;
+ }
+
+ return false;
+}
+
+bool
+SyncInterestTable::remove (DigestConstPtr digest)
+{
+ InterestContainer::index<hashed>::type::iterator item = m_table.get<hashed> ().find (digest);
+ if (item != m_table.get<hashed> ().end ())
+ {
+ m_table.get<hashed> ().erase (digest); // erase all records associated with the digest
+ return true;
+ }
+ return false;
+}
+
+void SyncInterestTable::expireInterests ()
+{
+ uint32_t count = 0;
+ ndn::time::Point expireTime = ndn::time::now() - m_entryLifetime;
+
+ while (m_table.size () > 0)
+ {
+ InterestContainer::index<timed>::type::iterator item = m_table.get<timed> ().begin ();
+
+ if (item->m_time <= expireTime)
+ {
+ m_table.get<timed> ().erase (item);
+ count ++;
+ }
+ else
+ break;
+ }
+}
+
+
+}
diff --git a/nsync/src/sync-interest-table.h b/nsync/src/sync-interest-table.h
new file mode 100644
index 0000000..9b7c46b
--- /dev/null
+++ b/nsync/src/sync-interest-table.h
@@ -0,0 +1,96 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ * Chaoyi Bian <bcy@pku.edu.cn>
+ * Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef SYNC_INTEREST_TABLE_H
+#define SYNC_INTEREST_TABLE_H
+
+#include <ndn-cpp-dev/util/scheduler.hpp>
+
+#include <string>
+#include <vector>
+
+#include "sync-digest.h"
+#include "sync-interest-container.h"
+
+namespace Sync {
+
+/**
+ * \ingroup sync
+ * @brief A table to keep unanswered Sync Interest
+ * all access operation to the table should grab the
+ * mutex first
+ */
+class SyncInterestTable
+{
+public:
+ SyncInterestTable (boost::asio::io_service& io, ndn::time::Duration lifetime);
+ ~SyncInterestTable ();
+
+ /**
+ * @brief Insert an interest, if interest already exists, update the
+ * timestamp
+ */
+ bool
+ insert (DigestConstPtr interest, const std::string &name, bool unknownState=false);
+
+ /**
+ * @brief Remove interest by digest (e.g., when it was satisfied)
+ */
+ bool
+ remove (DigestConstPtr interest);
+
+ /**
+ * @brief Remove interest by name (e.g., when it was satisfied)
+ */
+ bool
+ remove (const std::string &name);
+
+ /**
+ * @brief pop a non-expired Interest from PIT
+ */
+ Interest
+ pop ();
+
+ uint32_t
+ size () const;
+
+private:
+ /**
+ * @brief periodically called to expire Interest
+ */
+ void
+ expireInterests ();
+
+private:
+ ndn::time::Duration m_entryLifetime;
+ InterestContainer m_table;
+
+ ndn::Scheduler m_scheduler;
+};
+
+namespace Error {
+struct InterestTableIsEmpty : virtual boost::exception, virtual std::exception { };
+}
+
+} // Sync
+
+#endif // SYNC_INTEREST_TABLE_H
diff --git a/nsync/src/sync-leaf.cc b/nsync/src/sync-leaf.cc
new file mode 100644
index 0000000..03e2217
--- /dev/null
+++ b/nsync/src/sync-leaf.cc
@@ -0,0 +1,43 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ * Chaoyi Bian <bcy@pku.edu.cn>
+ * Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#include "sync-leaf.h"
+
+namespace Sync {
+
+Leaf::Leaf (NameInfoConstPtr info, const SeqNo &seq)
+ : m_info (info)
+ , m_seq (seq)
+{
+}
+
+Leaf::~Leaf ()
+{
+}
+
+void
+Leaf::setSeq (const SeqNo &seq)
+{
+ m_seq = std::max (m_seq, seq);
+}
+
+} // Sync
diff --git a/nsync/src/sync-leaf.h b/nsync/src/sync-leaf.h
new file mode 100644
index 0000000..345be46
--- /dev/null
+++ b/nsync/src/sync-leaf.h
@@ -0,0 +1,84 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ * Chaoyi Bian <bcy@pku.edu.cn>
+ * Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef SYNC_LEAF_H
+#define SYNC_LEAF_H
+
+#include "sync-seq-no.h"
+#include "sync-name-info.h"
+
+namespace Sync {
+
+/**
+ * \ingroup sync
+ * @brief Sync tree leaf
+ */
+class Leaf
+{
+public:
+ /**
+ * @brief Constructor
+ * @param info Smart pointer to leaf's name
+ * @param seq Initial sequence number of the pointer
+ */
+ Leaf (NameInfoConstPtr info, const SeqNo &seq);
+ virtual ~Leaf ();
+
+ /**
+ * @brief Get name of the leaf
+ */
+ NameInfoConstPtr
+ getInfo () const { return m_info; }
+
+ /**
+ * @brief Get sequence number of the leaf
+ */
+ const SeqNo&
+ getSeq () const { return m_seq; }
+
+ /**
+ * @brief Update sequence number of the leaf
+ * @param seq Sequence number
+ *
+ * Sequence number is updated to the largest value among this->m_seq and seq
+ */
+ virtual void
+ setSeq (const SeqNo &seq);
+
+private:
+ NameInfoConstPtr m_info;
+ SeqNo m_seq;
+};
+
+typedef boost::shared_ptr<Leaf> LeafPtr;
+typedef boost::shared_ptr<const Leaf> LeafConstPtr;
+
+inline std::ostream &
+operator << (std::ostream &os, const Leaf &leaf)
+{
+ os << *leaf.getInfo () << "(" << leaf.getSeq () << ")";
+ return os;
+}
+
+} // Sync
+
+#endif // SYNC_LEAF_H
diff --git a/nsync/src/sync-logging.cc b/nsync/src/sync-logging.cc
new file mode 100644
index 0000000..9048964
--- /dev/null
+++ b/nsync/src/sync-logging.cc
@@ -0,0 +1,61 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ * Chaoyi Bian <bcy@pku.edu.cn>
+ * Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#include "sync-logging.h"
+
+#ifdef HAVE_LOG4CXX
+
+#include <log4cxx/logger.h>
+#include <log4cxx/basicconfigurator.h>
+#include <log4cxx/consoleappender.h>
+#include <log4cxx/patternlayout.h>
+#include <log4cxx/level.h>
+#include <log4cxx/propertyconfigurator.h>
+#include <log4cxx/defaultconfigurator.h>
+#include <log4cxx/helpers/exception.h>
+using namespace log4cxx;
+using namespace log4cxx::helpers;
+
+#include <unistd.h>
+
+void
+INIT_LOGGERS ()
+{
+ static bool configured = false;
+
+ if (configured) return;
+
+ if (access ("log4cxx.properties", R_OK)==0)
+ PropertyConfigurator::configureAndWatch ("log4cxx.properties");
+ else
+ {
+ PatternLayoutPtr layout (new PatternLayout ("%d{HH:mm:ss} %p %c{1} - %m%n"));
+ ConsoleAppenderPtr appender (new ConsoleAppender (layout));
+
+ BasicConfigurator::configure( appender );
+ Logger::getRootLogger()->setLevel (log4cxx::Level::getInfo ());
+ }
+
+ configured = true;
+}
+
+#endif
diff --git a/nsync/src/sync-logging.h b/nsync/src/sync-logging.h
new file mode 100644
index 0000000..865204a
--- /dev/null
+++ b/nsync/src/sync-logging.h
@@ -0,0 +1,74 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ * Chaoyi Bian <bcy@pku.edu.cn>
+ * Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef SYNC_LOG_H
+#define SYNC_LOG_H
+
+#ifdef HAVE_LOG4CXX
+
+#include <log4cxx/logger.h>
+
+#define INIT_LOGGER(name) \
+ static log4cxx::LoggerPtr staticModuleLogger = log4cxx::Logger::getLogger (name);
+
+#define _LOG_DEBUG(x) \
+ LOG4CXX_DEBUG(staticModuleLogger, x);
+
+#define _LOG_TRACE(x) \
+ LOG4CXX_TRACE(staticModuleLogger, x);
+
+#define _LOG_FUNCTION(x) \
+ LOG4CXX_TRACE(staticModuleLogger, __FUNCTION__ << "(" << x << ")");
+
+#define _LOG_FUNCTION_NOARGS \
+ LOG4CXX_TRACE(staticModuleLogger, __FUNCTION__ << "()");
+
+#define _LOG_ERROR(x) \
+ LOG4CXX_ERROR(staticModuleLogger, x);
+
+void
+INIT_LOGGERS ();
+
+#else
+
+#define INIT_LOGGER(name)
+#define _LOG_FUNCTION(x)
+#define _LOG_FUNCTION_NOARGS
+#define _LOG_TRACE(x)
+#define INIT_LOGGERS(x)
+#define _LOG_ERROR(x)
+
+#ifdef _DEBUG
+
+#include <boost/date_time/posix_time/posix_time.hpp>
+#include <iostream>
+
+#define _LOG_DEBUG(x) \
+ std::clog << boost::get_system_time () << " " << boost::this_thread::get_id () << " " << x << endl;
+
+#else
+#define _LOG_DEBUG(x)
+#endif
+
+#endif // HAVE_LOG4CXX
+
+#endif // SYNC_LOG_H
diff --git a/nsync/src/sync-logic-event-container.h b/nsync/src/sync-logic-event-container.h
new file mode 100644
index 0000000..ebab72a
--- /dev/null
+++ b/nsync/src/sync-logic-event-container.h
@@ -0,0 +1,85 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ * Chaoyi Bian <bcy@pku.edu.cn>
+ * Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef SYNC_LOGIC_EVENT_CONTAINER_H
+#define SYNC_LOGIC_EVENT_CONTAINER_H
+
+#include "sync-event.h"
+
+#include <boost/function.hpp>
+#include <boost/date_time/posix_time/posix_time_types.hpp>
+
+#include <boost/multi_index_container.hpp>
+// #include <boost/multi_index/tag.hpp>
+#include <boost/multi_index/ordered_index.hpp>
+// #include <boost/multi_index/composite_key.hpp>
+// #include <boost/multi_index/hashed_index.hpp>
+// #include <boost/multi_index/random_access_index.hpp>
+#include <boost/multi_index/member.hpp>
+// #include <boost/multi_index/mem_fun.hpp>
+
+namespace mi = boost::multi_index;
+
+namespace Sync
+{
+
+struct LogicEvent
+{
+ LogicEvent (const boost::system_time &_time, Event _event, uint32_t _label)
+ : time (_time)
+ , event (_event)
+ , lbl (_label)
+ { }
+
+ boost::system_time time;
+ Event event;
+ uint32_t lbl;
+};
+
+/// @cond include_hidden
+struct byLabel { } ;
+/// @endcond
+
+/**
+ * \ingroup sync
+ * @brief ???
+ */
+struct EventsContainer : public mi::multi_index_container<
+ LogicEvent,
+ mi::indexed_by<
+
+ mi::ordered_non_unique<
+ mi::member<LogicEvent, boost::system_time, &LogicEvent::time>
+ >,
+
+ mi::ordered_non_unique<
+ mi::tag<byLabel>,
+ mi::member<LogicEvent, uint32_t, &LogicEvent::lbl>
+ >
+ >
+ >
+{
+};
+
+} // Sync
+
+#endif // SYNC_LOGIC_EVENT_CONTAINER_H
diff --git a/nsync/src/sync-logic.cc b/nsync/src/sync-logic.cc
new file mode 100644
index 0000000..ec4d63e
--- /dev/null
+++ b/nsync/src/sync-logic.cc
@@ -0,0 +1,705 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ * Chaoyi Bian <bcy@pku.edu.cn>
+ * Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ * Yingdi Yu <yingdi@cs.ucla.edu>
+ */
+
+#include "sync-logic.h"
+#include "sync-diff-leaf.h"
+#include "sync-full-leaf.h"
+#include "sync-logging.h"
+#include "sync-state.h"
+
+#include <boost/foreach.hpp>
+#include <boost/lexical_cast.hpp>
+#include <vector>
+
+using namespace std;
+using namespace ndn;
+
+INIT_LOGGER ("SyncLogic");
+
+
+#ifdef _DEBUG
+#define _LOG_DEBUG_ID(v) _LOG_DEBUG(m_instanceId << " " << v)
+#else
+#define _LOG_DEBUG_ID(v) _LOG_DEBUG(v)
+#endif
+
+#define GET_RANDOM(var) var ()
+
+#define TIME_SECONDS_WITH_JITTER(sec) \
+ (time::seconds(sec) + time::milliseconds(GET_RANDOM (m_reexpressionJitter)))
+
+#define TIME_MILLISECONDS_WITH_JITTER(ms) \
+ (time::seconds(ms) + time::milliseconds(GET_RANDOM (m_reexpressionJitter)))
+
+namespace Sync {
+
+using ndn::shared_ptr;
+
+int SyncLogic::m_instanceCounter = 0;
+
+SyncLogic::SyncLogic (const Name& syncPrefix,
+ shared_ptr<Validator> validator,
+ shared_ptr<Face> face,
+ LogicUpdateCallback onUpdate,
+ LogicRemoveCallback onRemove)
+ : m_state (new FullState)
+ , m_syncInterestTable (*face->ioService(), time::seconds(m_syncInterestReexpress))
+ , m_syncPrefix (syncPrefix)
+ , m_onUpdate (onUpdate)
+ , m_onRemove (onRemove)
+ , m_perBranch (false)
+ , m_validator(validator)
+ , m_keyChain(new KeyChain())
+ , m_face(face)
+ , m_scheduler(*face->ioService())
+ , m_randomGenerator (static_cast<unsigned int> (std::time (0)))
+ , m_rangeUniformRandom (m_randomGenerator, boost::uniform_int<> (200,1000))
+ , m_reexpressionJitter (m_randomGenerator, boost::uniform_int<> (100,500))
+ , m_recoveryRetransmissionInterval (m_defaultRecoveryRetransmitInterval)
+{
+ m_syncRegisteredPrefixId = m_face->setInterestFilter (m_syncPrefix,
+ bind(&SyncLogic::onSyncInterest, this, _1, _2),
+ bind(&SyncLogic::onSyncRegisterFailed, this, _1, _2));
+
+
+ m_reexpressingInterestId = m_scheduler.scheduleEvent (time::seconds (0), // no need to add jitter
+ bind (&SyncLogic::sendSyncInterest, this));
+
+ m_instanceId = string("Instance " + boost::lexical_cast<string>(m_instanceCounter++) + " ");
+}
+
+SyncLogic::SyncLogic (const Name& syncPrefix,
+ shared_ptr<Validator> validator,
+ shared_ptr<Face> face,
+ LogicPerBranchCallback onUpdateBranch)
+ : m_state (new FullState)
+ , m_syncInterestTable (*face->ioService(), time::seconds (m_syncInterestReexpress))
+ , m_syncPrefix (syncPrefix)
+ , m_onUpdateBranch (onUpdateBranch)
+ , m_perBranch(true)
+ , m_validator(validator)
+ , m_keyChain(new KeyChain())
+ , m_face(face)
+ , m_scheduler(*face->ioService())
+ , m_randomGenerator (static_cast<unsigned int> (std::time (0)))
+ , m_rangeUniformRandom (m_randomGenerator, boost::uniform_int<> (200,1000))
+ , m_reexpressionJitter (m_randomGenerator, boost::uniform_int<> (100,500))
+ , m_recoveryRetransmissionInterval (m_defaultRecoveryRetransmitInterval)
+{
+ m_syncRegisteredPrefixId = m_face->setInterestFilter (m_syncPrefix,
+ bind(&SyncLogic::onSyncInterest, this, _1, _2),
+ bind(&SyncLogic::onSyncRegisterFailed, this, _1, _2));
+
+ m_reexpressingInterestId = m_scheduler.scheduleEvent (time::seconds (0), // no need to add jitter
+ bind (&SyncLogic::sendSyncInterest, this));
+}
+
+SyncLogic::~SyncLogic ()
+{
+ m_face->unsetInterestFilter(m_syncRegisteredPrefixId);
+ m_scheduler.cancelEvent (m_reexpressingInterestId);
+ m_scheduler.cancelEvent (m_delayedInterestProcessingId);
+}
+
+/**
+ * Two types of intersts
+ *
+ * Normal name: .../<hash>
+ * Recovery name: .../recovery/<hash>
+ */
+boost::tuple<DigestConstPtr, std::string>
+SyncLogic::convertNameToDigestAndType (const Name &name)
+{
+ BOOST_ASSERT (m_syncPrefix.isPrefixOf(name));
+
+ int nameLengthDiff = name.size() - m_syncPrefix.size();
+ BOOST_ASSERT (nameLengthDiff > 0);
+ BOOST_ASSERT (nameLengthDiff < 3);
+
+ string hash = name.get(-1).toEscapedString();
+ string interestType;
+
+ if(nameLengthDiff == 1)
+ interestType = "normal";
+ else
+ interestType = name.get(-2).toEscapedString();
+
+ _LOG_DEBUG_ID (hash << ", " << interestType);
+
+ DigestPtr digest = boost::make_shared<Digest> ();
+ istringstream is (hash);
+ is >> *digest;
+
+ return make_tuple (digest, interestType);
+}
+
+void
+SyncLogic::onSyncInterest (const Name& prefix, const ndn::Interest& interest)
+{
+ Name name = interest.getName();
+
+ _LOG_DEBUG_ID("respondSyncInterest: " << name);
+
+ try
+ {
+ _LOG_DEBUG_ID ("<< I " << name);
+
+ DigestConstPtr digest;
+ string type;
+ tie (digest, type) = convertNameToDigestAndType (name);
+
+ if (type == "normal") // kind of ineffective...
+ {
+ processSyncInterest (name, digest);
+ }
+ else if (type == "recovery")
+ {
+ processSyncRecoveryInterest (name, digest);
+ }
+ }
+ catch (Error::DigestCalculationError &e)
+ {
+ _LOG_DEBUG_ID ("Something fishy happened...");
+ // log error. ignoring it for now, later we should log it
+ return ;
+ }
+}
+
+void
+SyncLogic::onSyncRegisterFailed(const Name& prefix, const string& msg)
+{
+ _LOG_DEBUG_ID("Sync prefix registration failed! " << msg);
+}
+
+void
+SyncLogic::onSyncData(const ndn::Interest& interest, Data& data)
+{
+ OnDataValidated onValidated = bind(&SyncLogic::onSyncDataValidated, this, _1);
+ OnDataValidationFailed onValidationFailed = bind(&SyncLogic::onSyncDataValidationFailed, this, _1);
+ m_validator->validate(data, onValidated, onValidationFailed);
+}
+
+void
+SyncLogic::onSyncTimeout(const ndn::Interest& interest)
+{
+ // It is OK. Others will handle the time out situation.
+}
+
+void
+SyncLogic::onSyncDataValidationFailed(const shared_ptr<const Data>& data)
+{
+ _LOG_DEBUG_ID("Sync data cannot be verified!");
+}
+
+void
+SyncLogic::onSyncDataValidated(const shared_ptr<const Data>& data)
+{
+ Name name = data->getName();
+ const char* wireData = (const char*)data->getContent().value();
+ size_t len = data->getContent().value_size();
+
+ try
+ {
+ _LOG_DEBUG_ID ("<< D " << name);
+
+ DigestConstPtr digest;
+ string type;
+ tie (digest, type) = convertNameToDigestAndType (name);
+
+ if (type == "normal")
+ {
+ processSyncData (name, digest, wireData, len);
+ }
+ else
+ {
+ // timer is always restarted when we schedule recovery
+ m_scheduler.cancelEvent (m_reexpressingRecoveryInterestId);
+ processSyncData (name, digest, wireData, len);
+ }
+ }
+ catch (Error::DigestCalculationError &e)
+ {
+ _LOG_DEBUG_ID ("Something fishy happened...");
+ // log error. ignoring it for now, later we should log it
+ return;
+ }
+}
+
+void
+SyncLogic::processSyncInterest (const Name &name, DigestConstPtr digest, bool timedProcessing/*=false*/)
+{
+ _LOG_DEBUG_ID("processSyncInterest");
+ DigestConstPtr rootDigest;
+ {
+ rootDigest = m_state->getDigest();
+ }
+
+ // Special case when state is not empty and we have received request with zero-root digest
+ if (digest->isZero () && !rootDigest->isZero ())
+ {
+
+ SyncStateMsg ssm;
+ {
+ ssm << (*m_state);
+ }
+ sendSyncData (name, digest, ssm);
+ return;
+ }
+
+ if (*rootDigest == *digest)
+ {
+ _LOG_DEBUG_ID ("processSyncInterest (): Same state. Adding to PIT");
+ m_syncInterestTable.insert (digest, name.toUri(), false);
+ return;
+ }
+
+ DiffStateContainer::iterator stateInDiffLog = m_log.find (digest);
+
+ if (stateInDiffLog != m_log.end ())
+ {
+ DiffStateConstPtr stateDiff = (*stateInDiffLog)->diff ();
+
+ sendSyncData (name, digest, stateDiff);
+ return;
+ }
+
+ if (!timedProcessing)
+ {
+ bool exists = m_syncInterestTable.insert (digest, name.toUri(), true);
+ if (exists) // somebody else replied, so restart random-game timer
+ {
+ _LOG_DEBUG_ID ("Unknown digest, but somebody may have already replied, so restart our timer");
+ m_scheduler.cancelEvent (m_delayedInterestProcessingId);
+ }
+
+ uint32_t waitDelay = GET_RANDOM (m_rangeUniformRandom);
+ _LOG_DEBUG_ID ("Digest is not in the log. Schedule processing after small delay: " << time::milliseconds (waitDelay));
+
+ m_delayedInterestProcessingId = m_scheduler.scheduleEvent (time::milliseconds (waitDelay),
+ bind (&SyncLogic::processSyncInterest, this, name, digest, true));
+ }
+ else
+ {
+ _LOG_DEBUG_ID (" (timed processing)");
+
+ m_recoveryRetransmissionInterval = m_defaultRecoveryRetransmitInterval;
+ sendSyncRecoveryInterests (digest);
+ }
+}
+
+void
+SyncLogic::processSyncData (const Name &name, DigestConstPtr digest, const char *wireData, size_t len)
+{
+ DiffStatePtr diffLog = boost::make_shared<DiffState> ();
+ bool ownInterestSatisfied = false;
+
+ try
+ {
+
+ m_syncInterestTable.remove (name.toUri()); // Remove satisfied interest from PIT
+
+ ownInterestSatisfied = (name == m_outstandingInterestName);
+
+ DiffState diff;
+ SyncStateMsg msg;
+ if (!msg.ParseFromArray(wireData, len) || !msg.IsInitialized())
+ {
+ //Throw
+ BOOST_THROW_EXCEPTION (Error::SyncStateMsgDecodingFailure () );
+ }
+ msg >> diff;
+
+ vector<MissingDataInfo> v;
+ BOOST_FOREACH (LeafConstPtr leaf, diff.getLeaves().get<ordered>())
+ {
+ DiffLeafConstPtr diffLeaf = boost::dynamic_pointer_cast<const DiffLeaf> (leaf);
+ BOOST_ASSERT (diffLeaf != 0);
+
+ NameInfoConstPtr info = diffLeaf->getInfo();
+ if (diffLeaf->getOperation() == UPDATE)
+ {
+ SeqNo seq = diffLeaf->getSeq();
+
+ bool inserted = false;
+ bool updated = false;
+ SeqNo oldSeq;
+ {
+ boost::tie (inserted, updated, oldSeq) = m_state->update (info, seq);
+ }
+
+ if (inserted || updated)
+ {
+ diffLog->update (info, seq);
+ if (!oldSeq.isValid())
+ {
+ oldSeq = SeqNo(seq.getSession(), 0);
+ }
+ else
+ {
+ ++oldSeq;
+ }
+ // there is no need for application to process update on forwarder node
+ if (info->toString() != forwarderPrefix)
+ {
+ MissingDataInfo mdi = {info->toString(), oldSeq, seq};
+ {
+ ostringstream interestName;
+ interestName << mdi.prefix << "/" << mdi.high.getSession() << "/" << mdi.high.getSeq();
+ _LOG_DEBUG_ID("+++++++++++++++ " + interestName.str());
+ }
+ if (m_perBranch)
+ {
+ ostringstream interestName;
+ interestName << mdi.prefix << "/" << mdi.high.getSession() << "/" << mdi.high.getSeq();
+ m_onUpdateBranch(interestName.str());
+ }
+ else
+ {
+ v.push_back(mdi);
+ }
+ }
+ }
+ }
+ else if (diffLeaf->getOperation() == REMOVE)
+ {
+ if (m_state->remove (info))
+ {
+ diffLog->remove (info);
+ if (!m_perBranch)
+ {
+ m_onRemove (info->toString ());
+ }
+ }
+ }
+ else
+ {
+ }
+ }
+
+ if (!v.empty())
+ {
+ if (!m_perBranch)
+ {
+ m_onUpdate(v);
+ }
+ }
+
+ insertToDiffLog (diffLog);
+ }
+ catch (Error::SyncStateMsgDecodingFailure &e)
+ {
+ _LOG_DEBUG_ID ("Something really fishy happened during state decoding " <<
+ diagnostic_information (e));
+ diffLog.reset ();
+ // don't do anything
+ }
+
+ if ((diffLog != 0 && diffLog->getLeaves ().size () > 0) ||
+ ownInterestSatisfied)
+ {
+ _LOG_DEBUG_ID(" +++++++++++++++ state changed!!!");
+ // Do it only if everything went fine and state changed
+
+ // this is kind of wrong
+ // satisfyPendingSyncInterests (diffLog); // if there are interests in PIT, there is a point to satisfy them using new state
+
+ // if state has changed, then it is safe to express a new interest
+ time::Duration after = time::milliseconds(GET_RANDOM (m_reexpressionJitter));
+ // cout << "------------ reexpress interest after: " << after << endl;
+ EventId eventId = m_scheduler.scheduleEvent (after,
+ bind (&SyncLogic::sendSyncInterest, this));
+
+ m_scheduler.cancelEvent (m_reexpressingInterestId);
+ m_reexpressingInterestId = eventId;
+ }
+}
+
+void
+SyncLogic::processSyncRecoveryInterest (const Name &name, DigestConstPtr digest)
+{
+ _LOG_DEBUG_ID("processSyncRecoveryInterest");
+ DiffStateContainer::iterator stateInDiffLog = m_log.find (digest);
+
+ if (stateInDiffLog == m_log.end ())
+ {
+ _LOG_DEBUG_ID ("Could not find " << *digest << " in digest log");
+ return;
+ }
+
+ SyncStateMsg ssm;
+ {
+ ssm << (*m_state);
+ }
+ sendSyncData (name, digest, ssm);
+}
+
+void
+SyncLogic::satisfyPendingSyncInterests (DiffStateConstPtr diffLog)
+{
+ DiffStatePtr fullStateLog = boost::make_shared<DiffState> ();
+ {
+ BOOST_FOREACH (LeafConstPtr leaf, m_state->getLeaves ()/*.get<timed> ()*/)
+ {
+ fullStateLog->update (leaf->getInfo (), leaf->getSeq ());
+ /// @todo Impose limit on how many state info should be send out
+ }
+ }
+
+ try
+ {
+ uint32_t counter = 0;
+ while (m_syncInterestTable.size () > 0)
+ {
+ Sync::Interest interest = m_syncInterestTable.pop ();
+
+ if (!interest.m_unknown)
+ {
+ _LOG_DEBUG_ID (">> D " << interest.m_name);
+ sendSyncData (interest.m_name, interest.m_digest, diffLog);
+ }
+ else
+ {
+ _LOG_DEBUG_ID (">> D (unknown)" << interest.m_name);
+ sendSyncData (interest.m_name, interest.m_digest, fullStateLog);
+ }
+ counter ++;
+ }
+ _LOG_DEBUG_ID ("Satisfied " << counter << " pending interests");
+ }
+ catch (Error::InterestTableIsEmpty &e)
+ {
+ // ok. not really an error
+ }
+}
+
+void
+SyncLogic::insertToDiffLog (DiffStatePtr diffLog)
+{
+ diffLog->setDigest (m_state->getDigest());
+ if (m_log.size () > 0)
+ {
+ m_log.get<sequenced> ().front ()->setNext (diffLog);
+ }
+ m_log.erase (m_state->getDigest()); // remove diff state with the same digest. next pointers are still valid
+ /// @todo Optimization
+ m_log.get<sequenced> ().push_front (diffLog);
+}
+
+void
+SyncLogic::addLocalNames (const Name &prefix, uint64_t session, uint64_t seq)
+{
+ DiffStatePtr diff;
+ {
+ //cout << "Add local names" <<endl;
+ NameInfoConstPtr info = StdNameInfo::FindOrCreate(prefix.toUri());
+
+ _LOG_DEBUG_ID ("addLocalNames (): old state " << *m_state->getDigest ());
+
+ SeqNo seqN (session, seq);
+ m_state->update(info, seqN);
+
+ _LOG_DEBUG_ID ("addLocalNames (): new state " << *m_state->getDigest ());
+
+ diff = boost::make_shared<DiffState>();
+ diff->update(info, seqN);
+ insertToDiffLog (diff);
+ }
+
+ // _LOG_DEBUG_ID ("PIT size: " << m_syncInterestTable.size ());
+ satisfyPendingSyncInterests (diff);
+}
+
+void
+SyncLogic::remove(const Name &prefix)
+{
+ DiffStatePtr diff;
+ {
+ NameInfoConstPtr info = StdNameInfo::FindOrCreate(prefix.toUri());
+ m_state->remove(info);
+
+ // increment the sequence number for the forwarder node
+ NameInfoConstPtr forwarderInfo = StdNameInfo::FindOrCreate(forwarderPrefix);
+
+ LeafContainer::iterator item = m_state->getLeaves ().find (forwarderInfo);
+ SeqNo seqNo (0);
+ if (item != m_state->getLeaves ().end ())
+ {
+ seqNo = (*item)->getSeq ();
+ ++seqNo;
+ }
+ m_state->update (forwarderInfo, seqNo);
+
+ diff = boost::make_shared<DiffState>();
+ diff->remove(info);
+ diff->update(forwarderInfo, seqNo);
+
+ insertToDiffLog (diff);
+ }
+
+ satisfyPendingSyncInterests (diff);
+}
+
+void
+SyncLogic::sendSyncInterest ()
+{
+ _LOG_DEBUG_ID("sendSyncInterest");
+
+ {
+ m_outstandingInterestName = m_syncPrefix;
+ ostringstream os;
+ os << *m_state->getDigest();
+ m_outstandingInterestName.append(os.str());
+ _LOG_DEBUG_ID (">> I " << m_outstandingInterestName);
+ }
+
+ _LOG_DEBUG_ID("sendSyncInterest: " << m_outstandingInterestName);
+
+ EventId eventId = m_scheduler.scheduleEvent (time::seconds(m_syncInterestReexpress) + time::milliseconds(GET_RANDOM (m_reexpressionJitter)),
+ bind (&SyncLogic::sendSyncInterest, this));
+ m_scheduler.cancelEvent (m_reexpressingInterestId);
+ m_reexpressingInterestId = eventId;
+
+ ndn::Interest interest(m_outstandingInterestName);
+ interest.setMustBeFresh(true);
+
+ m_face->expressInterest(interest,
+ bind(&SyncLogic::onSyncData, this, _1, _2),
+ bind(&SyncLogic::onSyncTimeout, this, _1));
+}
+
+void
+SyncLogic::sendSyncRecoveryInterests (DigestConstPtr digest)
+{
+ ostringstream os;
+ os << *digest;
+
+ Name interestName = m_syncPrefix;
+ interestName.append("recovery").append(os.str());
+
+ time::Duration nextRetransmission = time::milliseconds (m_recoveryRetransmissionInterval + GET_RANDOM (m_reexpressionJitter));
+
+ m_recoveryRetransmissionInterval <<= 1;
+
+ m_scheduler.cancelEvent (m_reexpressingRecoveryInterestId);
+ if (m_recoveryRetransmissionInterval < 100*1000) // <100 seconds
+ m_reexpressingRecoveryInterestId = m_scheduler.scheduleEvent (nextRetransmission,
+ bind (&SyncLogic::sendSyncRecoveryInterests, this, digest));
+
+ ndn::Interest interest(interestName);
+ interest.setMustBeFresh(true);
+
+ m_face->expressInterest(interest,
+ bind(&SyncLogic::onSyncData, this, _1, _2),
+ bind(&SyncLogic::onSyncTimeout, this, _1));
+}
+
+
+void
+SyncLogic::sendSyncData (const Name &name, DigestConstPtr digest, StateConstPtr state)
+{
+ SyncStateMsg msg;
+ msg << (*state);
+ sendSyncData(name, digest, msg);
+}
+
+// pass in state msg instead of state, so that there is no need to lock the state until
+// this function returns
+void
+SyncLogic::sendSyncData (const Name &name, DigestConstPtr digest, SyncStateMsg &ssm)
+{
+ _LOG_DEBUG_ID (">> D " << name);
+ int size = ssm.ByteSize();
+ char *wireData = new char[size];
+ ssm.SerializeToArray(wireData, size);
+
+ Data syncData(name);
+ syncData.setContent(reinterpret_cast<const uint8_t*>(wireData), size);
+ syncData.setFreshnessPeriod(m_syncResponseFreshness);
+
+ m_keyChain->sign(syncData);
+
+ m_face->put(syncData);
+
+ delete []wireData;
+
+ // checking if our own interest got satisfied
+ bool satisfiedOwnInterest = false;
+ {
+ satisfiedOwnInterest = (m_outstandingInterestName == name);
+ }
+
+ if (satisfiedOwnInterest)
+ {
+ _LOG_DEBUG_ID ("Satisfied our own Interest. Re-expressing (hopefully with a new digest)");
+
+ time::Duration after = time::milliseconds(GET_RANDOM (m_reexpressionJitter));
+ // cout << "------------ reexpress interest after: " << after << endl;
+ EventId eventId = m_scheduler.scheduleEvent (after,
+ bind (&SyncLogic::sendSyncInterest, this));
+ m_scheduler.cancelEvent (m_reexpressingInterestId);
+ m_reexpressingInterestId = eventId;
+ }
+}
+
+string
+SyncLogic::getRootDigest()
+{
+ ostringstream os;
+ os << *m_state->getDigest();
+ return os.str();
+}
+
+size_t
+SyncLogic::getNumberOfBranches () const
+{
+ return m_state->getLeaves ().size ();
+}
+
+void
+SyncLogic::printState () const
+{
+ BOOST_FOREACH (const boost::shared_ptr<Sync::Leaf> leaf, m_state->getLeaves ())
+ {
+ std::cout << *leaf << std::endl;
+ }
+}
+
+std::map<std::string, bool>
+SyncLogic::getBranchPrefixes() const
+{
+ std::map<std::string, bool> m;
+
+ BOOST_FOREACH (const boost::shared_ptr<Sync::Leaf> leaf, m_state->getLeaves ())
+ {
+ std::string prefix = leaf->getInfo()->toString();
+ // do not return forwarder prefix
+ if (prefix != forwarderPrefix)
+ {
+ m.insert(pair<std::string, bool>(prefix, false));
+ }
+ }
+
+ return m;
+}
+
+}
diff --git a/nsync/src/sync-logic.h b/nsync/src/sync-logic.h
new file mode 100644
index 0000000..fc63fca
--- /dev/null
+++ b/nsync/src/sync-logic.h
@@ -0,0 +1,218 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ * Chaoyi Bian <bcy@pku.edu.cn>
+ * Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ * Yingdi Yu <yingdi@cs.ucla.edu>
+ */
+
+#ifndef SYNC_LOGIC_H
+#define SYNC_LOGIC_H
+
+#include <boost/random.hpp>
+#include <memory>
+#include <map>
+
+#include <ndn-cpp-dev/face.hpp>
+#include <ndn-cpp-dev/security/validator.hpp>
+#include <ndn-cpp-dev/security/key-chain.hpp>
+#include <ndn-cpp-dev/util/scheduler.hpp>
+
+#include "sync-interest-table.h"
+#include "sync-diff-state.h"
+#include "sync-full-state.h"
+#include "sync-std-name-info.h"
+
+#include "sync-diff-state-container.h"
+
+#ifdef _DEBUG
+#ifdef HAVE_LOG4CXX
+#include <log4cxx/logger.h>
+#endif
+#endif
+
+namespace Sync {
+
+struct MissingDataInfo {
+ std::string prefix;
+ SeqNo low;
+ SeqNo high;
+};
+
+/**
+ * \ingroup sync
+ * @brief A wrapper for SyncApp, which handles ccnx related things (process
+ * interests and data)
+ */
+
+class SyncLogic
+{
+public:
+ //typedef boost::function< void ( const std::string &/*prefix*/, const SeqNo &/*newSeq*/, const SeqNo &/*oldSeq*/ ) > LogicUpdateCallback;
+ typedef boost::function< void (const std::vector<MissingDataInfo> & ) > LogicUpdateCallback;
+ typedef boost::function< void (const std::string &/*prefix*/ ) > LogicRemoveCallback;
+ typedef boost::function< void (const std::string &)> LogicPerBranchCallback;
+
+ /**
+ * @brief Constructor
+ * @param syncPrefix the name prefix to use for the Sync Interest
+ * @param onUpdate function that will be called when new state is detected
+ * @param onRemove function that will be called when state is removed
+ * @param ccnxHandle ccnx handle
+ * the app data when new remote names are learned
+ */
+ SyncLogic (const ndn::Name& syncPrefix,
+ ndn::shared_ptr<ndn::Validator> validator,
+ ndn::shared_ptr<ndn::Face> face,
+ LogicUpdateCallback onUpdate,
+ LogicRemoveCallback onRemove);
+
+ SyncLogic (const ndn::Name& syncPrefix,
+ ndn::shared_ptr<ndn::Validator> validator,
+ ndn::shared_ptr<ndn::Face> face,
+ LogicPerBranchCallback onUpdateBranch);
+
+ ~SyncLogic ();
+
+ /**
+ * a wrapper for the same func in SyncApp
+ */
+ void addLocalNames (const ndn::Name &prefix, uint64_t session, uint64_t seq);
+
+ /**
+ * @brief remove a participant's subtree from the sync tree
+ * @param prefix the name prefix for the participant
+ */
+ void remove (const ndn::Name &prefix);
+
+ std::string
+ getRootDigest();
+
+#ifdef _DEBUG
+ ndn::Scheduler &
+ getScheduler () { return m_scheduler; }
+#endif
+
+ void
+ printState () const;
+
+ std::map<std::string, bool>
+ getBranchPrefixes() const;
+
+private:
+ void
+ delayedChecksLoop ();
+
+ void
+ onSyncInterest (const ndn::Name& prefix, const ndn::Interest& interest);
+
+ void
+ onSyncRegisterFailed(const ndn::Name& prefix, const std::string& msg);
+
+ void
+ onSyncData(const ndn::Interest& interest, ndn::Data& data);
+
+ void
+ onSyncTimeout(const ndn::Interest& interest);
+
+ void
+ onSyncDataValidationFailed(const ndn::shared_ptr<const ndn::Data>& data);
+
+ void
+ onSyncDataValidated(const ndn::shared_ptr<const ndn::Data>& data);
+
+ void
+ processSyncInterest (const ndn::Name &name,
+ DigestConstPtr digest, bool timedProcessing=false);
+
+ void
+ processSyncData (const ndn::Name &name,
+ DigestConstPtr digest, const char *wireData, size_t len);
+
+ void
+ processSyncRecoveryInterest (const ndn::Name &name,
+ DigestConstPtr digest);
+
+ void
+ insertToDiffLog (DiffStatePtr diff);
+
+ void
+ satisfyPendingSyncInterests (DiffStateConstPtr diff);
+
+ boost::tuple<DigestConstPtr, std::string>
+ convertNameToDigestAndType (const ndn::Name &name);
+
+ void
+ sendSyncInterest ();
+
+ void
+ sendSyncRecoveryInterests (DigestConstPtr digest);
+
+ void
+ sendSyncData (const ndn::Name &name,
+ DigestConstPtr digest, StateConstPtr state);
+
+ void
+ sendSyncData (const ndn::Name &name,
+ DigestConstPtr digest, SyncStateMsg &msg);
+
+ size_t
+ getNumberOfBranches () const;
+
+private:
+ FullStatePtr m_state;
+ DiffStateContainer m_log;
+
+ ndn::Name m_outstandingInterestName;
+ SyncInterestTable m_syncInterestTable;
+
+ ndn::Name m_syncPrefix;
+ LogicUpdateCallback m_onUpdate;
+ LogicRemoveCallback m_onRemove;
+ LogicPerBranchCallback m_onUpdateBranch;
+ bool m_perBranch;
+ ndn::ptr_lib::shared_ptr<ndn::Validator> m_validator;
+ ndn::ptr_lib::shared_ptr<ndn::KeyChain> m_keyChain;
+ ndn::ptr_lib::shared_ptr<ndn::Face> m_face;
+ const ndn::RegisteredPrefixId* m_syncRegisteredPrefixId;
+
+ ndn::Scheduler m_scheduler;
+
+ boost::mt19937 m_randomGenerator;
+ boost::variate_generator<boost::mt19937&, boost::uniform_int<> > m_rangeUniformRandom;
+ boost::variate_generator<boost::mt19937&, boost::uniform_int<> > m_reexpressionJitter;
+
+ static const int m_unknownDigestStoreTime = 10; // seconds
+ static const int m_syncResponseFreshness = 1000; // MUST BE dividable by 1000!!!
+ static const int m_syncInterestReexpress = 4; // seconds
+
+ static const int m_defaultRecoveryRetransmitInterval = 200; // milliseconds
+ uint32_t m_recoveryRetransmissionInterval; // milliseconds
+
+ ndn::EventId m_delayedInterestProcessingId;
+ ndn::EventId m_reexpressingInterestId;
+ ndn::EventId m_reexpressingRecoveryInterestId;
+
+ std::string m_instanceId;
+ static int m_instanceCounter;
+};
+
+
+} // Sync
+
+#endif // SYNC_APP_WRAPPER_H
diff --git a/nsync/src/sync-name-info.cc b/nsync/src/sync-name-info.cc
new file mode 100644
index 0000000..30986cd
--- /dev/null
+++ b/nsync/src/sync-name-info.cc
@@ -0,0 +1,32 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ * Chaoyi Bian <bcy@pku.edu.cn>
+ * Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#include "sync-name-info.h"
+
+// #include <boost/lexical_cast.hpp>
+
+namespace Sync {
+
+NameInfo::NameMap NameInfo::m_names;
+size_t NameInfo::m_ids = 0;
+
+} // Sync
diff --git a/nsync/src/sync-name-info.h b/nsync/src/sync-name-info.h
new file mode 100644
index 0000000..2f7c165
--- /dev/null
+++ b/nsync/src/sync-name-info.h
@@ -0,0 +1,102 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ * Chaoyi Bian <bcy@pku.edu.cn>
+ * Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef SYNC_NAME_INFO_H
+#define SYNC_NAME_INFO_H
+
+#include <boost/shared_ptr.hpp>
+#include <boost/weak_ptr.hpp>
+#include <map>
+#include <string>
+#include "sync-digest.h"
+
+namespace Sync {
+
+/**
+ * @ingroup sync
+ * @brief Templated class for the leaf name
+ */
+class NameInfo
+{
+private:
+ typedef boost::weak_ptr<const NameInfo> const_weak_ptr;
+
+public:
+ virtual ~NameInfo () { };
+
+ /**
+ * @brief Get ID of the record (should be locally-unique, but not really necessary---this is be used for hashing purposes)
+ */
+ size_t
+ getHashId () const { return m_id; }
+
+ /**
+ * @brief Check if two names are equal
+ * @param info name to check with
+ */
+ virtual bool
+ operator == (const NameInfo &info) const = 0;
+
+ /**
+ * @brief Check if two names are in order
+ * @param info name to check with
+ */
+ virtual bool
+ operator < (const NameInfo &info) const = 0;
+
+ /**
+ * @brief Calculates digest of the name
+ */
+ const Digest &
+ getDigest () const { return m_digest; }
+
+ /**
+ * @brief Convert prefix to string
+ * @returns string representation of prefix
+ */
+ virtual std::string
+ toString () const = 0;
+
+protected:
+ // actual stuff
+ size_t m_id; ///< @brief Identifies NameInfo throughout the library (for hash container, doesn't need to be strictly unique)
+ Digest m_digest;
+
+ // static stuff
+ typedef std::map<std::string, const_weak_ptr> NameMap;
+ static size_t m_ids;
+ static NameMap m_names;
+};
+
+typedef boost::shared_ptr<NameInfo> NameInfoPtr;
+typedef boost::shared_ptr<const NameInfo> NameInfoConstPtr;
+
+inline std::ostream &
+operator << (std::ostream &os, const NameInfo &info)
+{
+ os << info.toString ();
+ return os;
+}
+
+} // Sync
+
+#endif // SYNC_NAME_INFO_H
diff --git a/nsync/src/sync-seq-no.cc b/nsync/src/sync-seq-no.cc
new file mode 100644
index 0000000..fbbc53f
--- /dev/null
+++ b/nsync/src/sync-seq-no.cc
@@ -0,0 +1,39 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ * Chaoyi Bian <bcy@pku.edu.cn>
+ * Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#include "sync-seq-no.h"
+#include <boost/make_shared.hpp>
+
+using namespace boost;
+
+namespace Sync {
+
+DigestConstPtr
+SeqNo::getDigest () const
+{
+ DigestPtr digest = make_shared<Digest> ();
+ *digest << m_session << m_seq;
+ digest->finalize ();
+ return digest;
+}
+
+} // Sync
diff --git a/nsync/src/sync-seq-no.h b/nsync/src/sync-seq-no.h
new file mode 100644
index 0000000..bf21704
--- /dev/null
+++ b/nsync/src/sync-seq-no.h
@@ -0,0 +1,198 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ * Chaoyi Bian <bcy@pku.edu.cn>
+ * Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ * Yingdi Yu <yingdi@cs.ucla.edu>
+ */
+
+#ifndef SYNC_SEQ_NO_H
+#define SYNC_SEQ_NO_H
+
+#include <boost/cstdint.hpp>
+#include "sync-digest.h"
+
+namespace Sync {
+
+/**
+ * @ingroup sync
+ * @brief Sequence number abstraction
+ */
+class SeqNo
+{
+public:
+ /**
+ * @brief Default constructor. Creates an zero sequence number with zero session ID (basically is an invalid object)
+ */
+ SeqNo ()
+ : m_valid (false)
+ , m_session (0)
+ , m_seq (0)
+ {
+ }
+
+ /**
+ * @brief Copy constructor
+ * @param seq sequence number object to copy from
+ */
+ SeqNo (const SeqNo &seq)
+ {
+ *this = seq;
+ }
+
+ /**
+ * @brief Assignment operator
+ * @param seq sequence number object to copy from
+ */
+ SeqNo &
+ operator = (const SeqNo &seq)
+ {
+ m_valid = seq.m_valid;
+ m_session = seq.m_session;
+ m_seq = seq.m_seq;
+
+ return *this;
+ }
+
+ /**
+ * @brief Constructor with just sequence number. Session assumed to be zero
+ * @param seq Sequence number
+ */
+ SeqNo (uint64_t seq)
+ : m_valid (true)
+ , m_session (0)
+ , m_seq (seq)
+ { }
+
+ /**
+ * @brief Constructor with session and sequence id
+ * @param session Session ID
+ * @param seq Sequence number
+ */
+ SeqNo (uint64_t session, uint64_t seq)
+ : m_valid (true)
+ , m_session (session)
+ , m_seq (seq)
+ { }
+
+ /**
+ * @brief Get sequence number digest
+ *
+ * Digest will be calculated every time it is requested
+ */
+ DigestConstPtr
+ getDigest () const;
+
+ /**
+ * @brief Compare if one sequence number is lower
+ * @param seq Another sequence number to compare with
+ *
+ * tuple (session1, seq1) is less than (session2, seq2) in two cases:
+ * 1. session1 < session2
+ * 2. session1 == session2 and seq1 < seq2
+ */
+ bool
+ operator < (const SeqNo &seq) const
+ {
+ return m_session < seq.m_session || (m_session == seq.m_session && m_seq < seq.m_seq);
+ }
+
+ /**
+ * @brief Compare if two sequence numbers are equal
+ * @param seq Another sequence number to compare with
+ */
+ bool
+ operator == (const SeqNo &seq) const
+ {
+ return m_session == seq.m_session && m_seq == seq.m_seq;
+ }
+
+ bool
+ operator <= (const SeqNo &seq) const
+ {
+ return m_session == seq.m_session && m_seq <= seq.m_seq;
+ }
+
+ SeqNo &
+ operator ++ ()
+ {
+ if (m_valid) {
+ m_seq ++;
+ }
+ else {
+ m_valid = true;
+ }
+ return *this;
+ }
+
+ bool
+ isValid () const
+ {
+ return m_valid;
+ }
+
+ /**
+ * @brief Get session id
+ */
+ uint64_t getSession () const
+ { return m_session; }
+
+ /**
+ * @brief Get sequence number
+ */
+ uint64_t getSeq () const
+ { return m_seq; }
+
+ /**
+ * @brief Set sequence number
+ */
+ void
+ setSeq(uint64_t seq)
+ { m_seq = seq; }
+
+private:
+ bool m_valid;
+
+ /**
+ * @brief Session ID (e.g., after crash, application will choose new session ID.
+ *
+ * Note that session IDs for the same name should always increase. So, the good choice
+ * for the session ID is client's timestamp
+ */
+ uint64_t m_session;
+
+ /**
+ * @brief Sequence number
+ *
+ * Sequence number for a session always starts with 0 and goes to max value.
+ *
+ * For now, wrapping sequence number after max to zero is not supported
+ */
+ uint64_t m_seq;
+};
+
+inline std::ostream &
+operator << (std::ostream &os, const SeqNo &seqno)
+{
+ os << "<session>" << seqno.getSession () << "</session><seqno>" << seqno.getSeq () << "</seqno>";
+ return os;
+}
+
+} // Sync
+
+#endif // SYNC_SEQ_NO_H
diff --git a/nsync/src/sync-socket.cc b/nsync/src/sync-socket.cc
new file mode 100644
index 0000000..db51ce2
--- /dev/null
+++ b/nsync/src/sync-socket.cc
@@ -0,0 +1,155 @@
+/* -*- Mode: C32++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Yingdi Yu <yingdi@cs.ucla.edu>
+ */
+
+#include "sync-socket.h"
+#include "sync-logging.h"
+
+using namespace std;
+using namespace ndn;
+
+INIT_LOGGER ("SyncSocket");
+
+namespace Sync {
+
+using ndn::shared_ptr;
+
+SyncSocket::SyncSocket (const Name &syncPrefix,
+ shared_ptr<Validator> validator,
+ shared_ptr<Face> face,
+ NewDataCallback dataCallback,
+ RemoveCallback rmCallback )
+ : m_newDataCallback(dataCallback)
+ , m_validator(validator)
+ , m_keyChain(new KeyChain())
+ , m_face(face)
+ , m_ioService(face->ioService())
+ , m_syncLogic (syncPrefix,
+ validator,
+ face,
+ bind(&SyncSocket::passCallback, this, _1),
+ rmCallback)
+{}
+
+SyncSocket::~SyncSocket()
+{
+}
+
+bool
+SyncSocket::publishData(const Name &prefix, uint64_t session, const char *buf, size_t len, int freshness,uint64_t seq)
+{
+ shared_ptr<Data> data = make_shared<Data>();
+ data->setContent(reinterpret_cast<const uint8_t*>(buf), len);
+ data->setFreshnessPeriod(1000*freshness);
+
+ m_ioService->post(bind(&SyncSocket::publishDataInternal, this, data, prefix, session,seq));
+
+ return true;
+}
+
+void
+SyncSocket::publishDataInternal(shared_ptr<Data> data, const Name &prefix, uint64_t session,uint64_t seq)
+{
+ uint64_t sequence = seq;
+ Name dataName = prefix;
+ dataName.append(boost::lexical_cast<string>(session)).append(boost::lexical_cast<string>(sequence));
+ data->setName(dataName);
+
+ m_keyChain->sign(*data);
+ m_face->put(*data);
+
+ SeqNo s(session, sequence + 1);
+
+ m_sequenceLog[prefix] = s;
+ m_syncLogic.addLocalNames (prefix, session, sequence);
+}
+
+void
+SyncSocket::fetchData(const Name &prefix, const SeqNo &seq, const OnDataValidated& onValidated, int retry)
+{
+ Name interestName = prefix;
+ interestName.append(boost::lexical_cast<string>(seq.getSession())).append(boost::lexical_cast<string>(seq.getSeq()));
+
+ const OnDataValidationFailed& onValidationFailed = bind(&SyncSocket::onDataValidationFailed, this, _1);
+
+ ndn::Interest interest(interestName);
+ interest.setMustBeFresh(true);
+ m_face->expressInterest(interest,
+ bind(&SyncSocket::onData, this, _1, _2, onValidated, onValidationFailed),
+ bind(&SyncSocket::onDataTimeout, this, _1, retry, onValidated, onValidationFailed));
+
+}
+
+void
+SyncSocket::onData(const ndn::Interest& interest, Data& data,
+ const OnDataValidated& onValidated,
+ const OnDataValidationFailed& onValidationFailed)
+{
+ m_validator->validate(data, onValidated, onValidationFailed);
+}
+
+void
+SyncSocket::onDataTimeout(const ndn::Interest& interest,
+ int retry,
+ const OnDataValidated& onValidated,
+ const OnDataValidationFailed& onValidationFailed)
+{
+ if(retry > 0)
+ {
+ m_face->expressInterest(interest,
+ bind(&SyncSocket::onData,
+ this,
+ _1,
+ _2,
+ onValidated,
+ onValidationFailed),
+ bind(&SyncSocket::onDataTimeout,
+ this,
+ _1,
+ retry - 1,
+ onValidated,
+ onValidationFailed));
+
+ }
+ else
+ _LOG_DEBUG("interest eventually time out!");
+}
+
+void
+SyncSocket::onDataValidationFailed(const shared_ptr<const Data>& data)
+{
+ _LOG_DEBUG("data cannot be verified!");
+}
+
+
+uint64_t
+SyncSocket::getNextSeq (const Name &prefix, uint64_t session)
+{
+ SequenceLog::iterator i = m_sequenceLog.find (prefix);
+
+ if (i != m_sequenceLog.end ())
+ {
+ SeqNo s = i->second;
+ if (s.getSession() == session)
+ return s.getSeq();
+ }
+ return 0;
+}
+
+}//Sync
diff --git a/nsync/src/sync-socket.h b/nsync/src/sync-socket.h
new file mode 100644
index 0000000..e4eec37
--- /dev/null
+++ b/nsync/src/sync-socket.h
@@ -0,0 +1,128 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Yingdi Yu <yingdi@cs.ucla.edu>
+ */
+
+#ifndef _SYNC_SOCKET_H
+#define _SYNC_SOCKET_H
+
+#include <ndn-cpp-dev/face.hpp>
+#include <ndn-cpp-dev/security/validator.hpp>
+#include <ndn-cpp-dev/security/key-chain.hpp>
+
+#include "sync-logic.h"
+#include "sync-seq-no.h"
+
+#include <utility>
+#include <map>
+#include <vector>
+#include <sstream>
+
+namespace Sync {
+
+/**
+ * \ingroup sync
+ * @brief A simple interface to interact with client code
+ */
+class SyncSocket
+{
+public:
+ typedef ndn::function< void (const std::vector<MissingDataInfo> &, SyncSocket * ) > NewDataCallback;
+ typedef ndn::function< void (const std::string &/*prefix*/ ) > RemoveCallback;
+
+ /**
+ * @brief the constructor for SyncAppSocket; the parameter syncPrefix
+ * should be passed to the constructor of m_syncAppWrapper; the other
+ * parameter should be passed to the constructor of m_fetcher; furthermore,
+ * the fetch function of m_fetcher should be a second paramter passed to
+ * the constructor of m_syncAppWrapper, so that m_syncAppWrapper can tell
+ * m_fetcher to fetch the actual app data after it learns the names
+ *
+ * @param syncPrefix the name prefix for Sync Interest
+ * @param dataCallback the callback to process data
+ */
+ SyncSocket (const ndn::Name &syncPrefix,
+ ndn::shared_ptr<ndn::Validator> validator,
+ ndn::shared_ptr<ndn::Face> face,
+ NewDataCallback dataCallback,
+ RemoveCallback rmCallback);
+
+ ~SyncSocket ();
+
+ bool
+ publishData(const ndn::Name &prefix, uint64_t session, const char *buf, size_t len, int freshness,uint64_t seq);
+
+ void
+ remove (const ndn::Name &prefix)
+ { m_syncLogic.remove(prefix); }
+
+ void
+ fetchData(const ndn::Name &prefix, const SeqNo &seq, const ndn::OnDataValidated& onValidated, int retry = 0);
+
+ std::string
+ getRootDigest()
+ { return m_syncLogic.getRootDigest(); }
+
+ uint64_t
+ getNextSeq (const ndn::Name &prefix, uint64_t session);
+
+ SyncLogic &
+ getLogic ()
+ { return m_syncLogic; }
+
+ // make this a static function so we don't have to create socket instance without
+ // knowing the local prefix. it's a wrong place for this function anyway
+ static std::string
+ GetLocalPrefix ();
+
+private:
+ void
+ publishDataInternal(ndn::shared_ptr<ndn::Data> data, const ndn::Name &prefix, uint64_t session,uint64_t seq);
+
+ void
+ passCallback(const std::vector<MissingDataInfo> &v)
+ { m_newDataCallback(v, this); }
+
+ void
+ onData(const ndn::Interest& interest, ndn::Data& data,
+ const ndn::OnDataValidated& onValidated,
+ const ndn::OnDataValidationFailed& onValidationFailed);
+
+ void
+ onDataTimeout(const ndn::Interest& interest,
+ int retry,
+ const ndn::OnDataValidated& onValidated,
+ const ndn::OnDataValidationFailed& onValidationFailed);
+
+ void
+ onDataValidationFailed(const ndn::shared_ptr<const ndn::Data>& data);
+
+private:
+ typedef std::map<ndn::Name, SeqNo> SequenceLog;
+ NewDataCallback m_newDataCallback;
+ SequenceLog m_sequenceLog;
+ ndn::shared_ptr<ndn::Validator> m_validator;
+ ndn::shared_ptr<ndn::KeyChain> m_keyChain;
+ ndn::shared_ptr<ndn::Face> m_face;
+ ndn::shared_ptr<boost::asio::io_service> m_ioService;
+ SyncLogic m_syncLogic;
+};
+
+} // Sync
+
+#endif // SYNC_SOCKET_H
diff --git a/nsync/src/sync-state-leaf-container.h b/nsync/src/sync-state-leaf-container.h
new file mode 100644
index 0000000..48819aa
--- /dev/null
+++ b/nsync/src/sync-state-leaf-container.h
@@ -0,0 +1,101 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ * Chaoyi Bian <bcy@pku.edu.cn>
+ * Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef SYNC_STATE_LEAF_CONTAINER
+#define SYNC_STATE_LEAF_CONTAINER
+
+#include "sync-leaf.h"
+#include "sync-name-info.h"
+
+#include <boost/multi_index_container.hpp>
+// #include <boost/multi_index/tag.hpp>
+#include <boost/multi_index/ordered_index.hpp>
+// #include <boost/multi_index/composite_key.hpp>
+#include <boost/multi_index/hashed_index.hpp>
+// #include <boost/multi_index/random_access_index.hpp>
+// #include <boost/multi_index/member.hpp>
+#include <boost/multi_index/mem_fun.hpp>
+
+namespace mi = boost::multi_index;
+
+namespace Sync {
+
+struct NameInfoHash : public std::unary_function<NameInfo, std::size_t>
+{
+ std::size_t
+ operator() (NameInfoConstPtr prefix) const
+ {
+ return prefix->getHashId ();
+ }
+};
+
+struct NameInfoEqual : public std::unary_function<NameInfo, std::size_t>
+{
+ bool
+ operator() (NameInfoConstPtr prefix1, NameInfoConstPtr prefix2) const
+ {
+ return *prefix1 == *prefix2;
+ }
+};
+
+struct NameInfoCompare : public std::unary_function<NameInfo, std::size_t>
+{
+ bool
+ operator() (NameInfoConstPtr prefix1, NameInfoConstPtr prefix2) const
+ {
+ return *prefix1 < *prefix2;
+ }
+};
+
+/// @cond include_hidden
+struct hashed { };
+struct ordered { };
+/// @endcond
+
+/**
+ * \ingroup sync
+ * @brief Container for SYNC leaves
+ */
+struct LeafContainer : public mi::multi_index_container<
+ LeafPtr,
+ mi::indexed_by<
+ // For fast access to elements using NameInfo
+ mi::hashed_unique<
+ mi::tag<hashed>,
+ mi::const_mem_fun<Leaf, NameInfoConstPtr, &Leaf::getInfo>,
+ NameInfoHash,
+ NameInfoEqual
+ >,
+
+ mi::ordered_unique<
+ mi::tag<ordered>,
+ mi::const_mem_fun<Leaf, NameInfoConstPtr, &Leaf::getInfo>,
+ NameInfoCompare
+ >
+ >
+ >
+{
+};
+
+} // Sync
+
+#endif // SYNC_STATE_LEAF_CONTAINER
diff --git a/nsync/src/sync-state.cc b/nsync/src/sync-state.cc
new file mode 100644
index 0000000..6c374a4
--- /dev/null
+++ b/nsync/src/sync-state.cc
@@ -0,0 +1,172 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ * Chaoyi Bian <bcy@pku.edu.cn>
+ * Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#include "sync-state.h"
+#include "sync-diff-leaf.h"
+#include "sync-std-name-info.h"
+
+#include <boost/assert.hpp>
+#include <boost/foreach.hpp>
+#include <boost/shared_ptr.hpp>
+#include <boost/throw_exception.hpp>
+#include <boost/lexical_cast.hpp>
+
+// using namespace std;
+using namespace boost;
+
+typedef error_info<struct tag_errmsg, std::string> info_str;
+
+using namespace Sync::Error;
+
+namespace Sync {
+
+/*
+std::ostream &
+operator << (std::ostream &os, const State &state)
+{
+ os << "<state>"; DEBUG_ENDL;
+
+ BOOST_FOREACH (shared_ptr<const Leaf> leaf, state.getLeaves ().get<ordered> ())
+ {
+ shared_ptr<const DiffLeaf> diffLeaf = dynamic_pointer_cast<const DiffLeaf> (leaf);
+ if (diffLeaf != 0)
+ {
+ os << "<item action=\"" << diffLeaf->getOperation () << "\">"; DEBUG_ENDL;
+ }
+ else
+ {
+ os << "<item>"; DEBUG_ENDL;
+ }
+ os << "<name>" << *leaf->getInfo () << "</name>"; DEBUG_ENDL;
+ if (diffLeaf == 0 || (diffLeaf != 0 && diffLeaf->getOperation () == UPDATE))
+ {
+ os << "<seq>" << leaf->getSeq () << "</seq>"; DEBUG_ENDL;
+ }
+ os << "</item>"; DEBUG_ENDL;
+ }
+ os << "</state>";
+}
+*/
+
+SyncStateMsg &
+operator << (SyncStateMsg &ossm, const State &state)
+{
+ BOOST_FOREACH (shared_ptr<const Leaf> leaf, state.getLeaves ().get<ordered> ())
+ {
+ SyncState *oss = ossm.add_ss();
+ shared_ptr<const DiffLeaf> diffLeaf = dynamic_pointer_cast<const DiffLeaf> (leaf);
+ if (diffLeaf != 0 && diffLeaf->getOperation() != UPDATE)
+ {
+ oss->set_type(SyncState::DELETE);
+ }
+ else
+ {
+ oss->set_type(SyncState::UPDATE);
+ }
+
+ std::ostringstream os;
+ os << *leaf->getInfo();
+ oss->set_name(os.str());
+
+ if (diffLeaf == 0 || (diffLeaf != 0 && diffLeaf->getOperation () == UPDATE))
+ {
+ SyncState::SeqNo *seqNo = oss->mutable_seqno();
+ seqNo->set_session(leaf->getSeq().getSession());
+ seqNo->set_seq(leaf->getSeq().getSeq());
+ }
+ }
+ return ossm;
+}
+
+/*
+std::istream &
+operator >> (std::istream &in, State &state)
+{
+ TiXmlDocument doc;
+ in >> doc;
+
+ if (doc.RootElement() == 0)
+ BOOST_THROW_EXCEPTION (SyncXmlDecodingFailure () << info_str ("Empty XML"));
+
+ for (TiXmlElement *iterator = doc.RootElement()->FirstChildElement ("item");
+ iterator != 0;
+ iterator = iterator->NextSiblingElement("item"))
+ {
+ TiXmlElement *name = iterator->FirstChildElement ("name");
+ if (name == 0 || name->GetText() == 0)
+ BOOST_THROW_EXCEPTION (SyncXmlDecodingFailure () << info_str ("<name> element is missing"));
+
+ NameInfoConstPtr info = StdNameInfo::FindOrCreate (name->GetText());
+
+ if (iterator->Attribute("action") == 0 || strcmp(iterator->Attribute("action"), "update") == 0)
+ {
+ TiXmlElement *seq = iterator->FirstChildElement ("seq");
+ if (seq == 0)
+ BOOST_THROW_EXCEPTION (SyncXmlDecodingFailure () << info_str ("<seq> element is missing"));
+
+ TiXmlElement *session = seq->FirstChildElement ("session");
+ TiXmlElement *seqno = seq->FirstChildElement ("seqno");
+
+ if (session == 0 || session->GetText() == 0)
+ BOOST_THROW_EXCEPTION (SyncXmlDecodingFailure () << info_str ("<session> element is missing"));
+ if (seqno == 0 || seqno->GetText() == 0)
+ BOOST_THROW_EXCEPTION (SyncXmlDecodingFailure () << info_str ("<seqno> element is missing"));
+
+ state.update (info, SeqNo (
+ lexical_cast<uint32_t> (session->GetText()),
+ lexical_cast<uint32_t> (seqno->GetText())
+ ));
+ }
+ else
+ {
+ state.remove (info);
+ }
+ }
+
+ return in;
+}
+*/
+
+SyncStateMsg &
+operator >> (SyncStateMsg &issm, State &state)
+{
+ int n = issm.ss_size();
+ for (int i = 0; i < n; i++)
+ {
+ const SyncState &ss = issm.ss(i);
+ NameInfoConstPtr info = StdNameInfo::FindOrCreate (ss.name());
+ if (ss.type() == SyncState::UPDATE)
+ {
+ uint64_t session = lexical_cast<uint64_t>(ss.seqno().session());
+ uint64_t seq = lexical_cast<uint64_t>(ss.seqno().seq());
+ SeqNo seqNo(session, seq);
+ state.update(info, seqNo);
+ }
+ else
+ {
+ state.remove(info);
+ }
+ }
+ return issm;
+}
+
+}
diff --git a/nsync/src/sync-state.h b/nsync/src/sync-state.h
new file mode 100644
index 0000000..54ac9d9
--- /dev/null
+++ b/nsync/src/sync-state.h
@@ -0,0 +1,117 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ * Chaoyi Bian <bcy@pku.edu.cn>
+ * Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef SYNC_STATE_H
+#define SYNC_STATE_H
+
+#include "sync-state-leaf-container.h"
+#include <boost/exception/all.hpp>
+#include "boost/tuple/tuple.hpp"
+#include "sync-state.pb.h"
+
+/**
+ * \defgroup sync SYNC protocol
+ *
+ * Implementation of SYNC protocol
+ */
+namespace Sync {
+
+/**
+ * \ingroup sync
+ * @brief this prefix will be used for the dummy node which increases its sequence number whenever
+ * a remove operation happens; this is to prevent the reversion of root digest when we prune
+ * a branch, i.e. help the root digest to be forward only
+ * No corresponding data msg would be published and no attempt would be made to retrieve the
+ * data msg
+ */
+const std::string forwarderPrefix = "/d0n0t18ak/t0ps8cr8t";
+
+class State;
+typedef boost::shared_ptr<State> StatePtr;
+typedef boost::shared_ptr<State> StateConstPtr;
+
+/**
+ * \ingroup sync
+ * @brief Container for state leaves and definition of the abstract interface to work with State objects
+ */
+class State
+{
+public:
+ virtual ~State () { };
+
+ /**
+ * @brief Add or update leaf to the state tree
+ *
+ * @param info name of the leaf
+ * @param seq sequence number of the leaf
+ */
+ virtual boost::tuple<bool/*inserted*/, bool/*updated*/, SeqNo/*oldSeqNo*/>
+ update (NameInfoConstPtr info, const SeqNo &seq) = 0;
+
+ /**
+ * @brief Remove leaf from the state tree
+ * @param info name of the leaf
+ */
+ virtual bool
+ remove (NameInfoConstPtr info) = 0;
+
+ /**
+ * @brief Get state leaves
+ */
+ const LeafContainer &
+ getLeaves () const
+ { return m_leaves; }
+
+protected:
+ LeafContainer m_leaves;
+};
+
+
+/**
+ * @brief Formats a protobuf SyncStateMsg msg
+ * @param oss output SyncStateMsg msg
+ * @param state state
+ * @returns output SyncStateMsg msg
+ */
+SyncStateMsg &
+operator << (SyncStateMsg &ossm, const State &state);
+
+
+/**
+ * @brief Parse a protobuf SyncStateMsg msg
+ * @param iss input SyncStateMsg msg
+ * @param state state
+ * @returns SyncStateMsg msg
+ */
+SyncStateMsg &
+operator >> (SyncStateMsg &issm, State &state);
+
+namespace Error {
+/**
+ * @brief Will be thrown when data cannot be properly decoded to SyncStateMsg
+ */
+struct SyncStateMsgDecodingFailure : virtual boost::exception, virtual std::exception { };
+}
+
+} // Sync
+
+#endif // SYNC_STATE_H
diff --git a/nsync/src/sync-state.proto b/nsync/src/sync-state.proto
new file mode 100644
index 0000000..7cc6b18
--- /dev/null
+++ b/nsync/src/sync-state.proto
@@ -0,0 +1,24 @@
+package Sync;
+
+message SyncState
+{
+ required string name = 1;
+ enum ActionType
+ {
+ UPDATE = 0;
+ DELETE = 1;
+ OTHER = 2;
+ }
+ required ActionType type = 2;
+ message SeqNo
+ {
+ required uint64 seq = 1;
+ required uint64 session = 2;
+ }
+ optional SeqNo seqno = 3;
+}
+
+message SyncStateMsg
+{
+ repeated SyncState ss = 1;
+}
diff --git a/nsync/src/sync-std-name-info.cc b/nsync/src/sync-std-name-info.cc
new file mode 100644
index 0000000..2c0313d
--- /dev/null
+++ b/nsync/src/sync-std-name-info.cc
@@ -0,0 +1,92 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ * Chaoyi Bian <bcy@pku.edu.cn>
+ * Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#include "sync-std-name-info.h"
+
+// using namespace std;
+using namespace boost;
+
+namespace Sync {
+
+
+NameInfoConstPtr
+StdNameInfo::FindOrCreate (const std::string &key)
+{
+ // std::cout << "FindOrCreate: " << m_names.size () << "\n";
+
+ NameInfoConstPtr ret;
+
+ NameMap::iterator item = m_names.find (key);
+ if (item != m_names.end ())
+ {
+ ret = item->second.lock ();
+ BOOST_ASSERT (ret != 0);
+ }
+ else
+ {
+ ret = NameInfoPtr (new StdNameInfo (key));
+ weak_ptr<const NameInfo> value (ret);
+ std::pair<NameMap::iterator,bool> inserted =
+ m_names.insert (make_pair (key, value));
+
+ BOOST_ASSERT (inserted.second); // previous call has to insert value
+ item = inserted.first;
+ }
+
+ return ret;
+}
+
+StdNameInfo::StdNameInfo (const std::string &name)
+ : m_name (name)
+{
+ m_id = m_ids ++; // set ID for a newly inserted element
+ m_digest << name;
+ m_digest.finalize ();
+
+ // std::cout << "StdNameInfo: " << name << " = " << m_id << "\n";
+}
+
+StdNameInfo::~StdNameInfo ()
+{
+ // cout << "Destructor for " << m_name << "\n";
+ m_names.erase (toString ());
+}
+
+std::string
+StdNameInfo::toString () const
+{
+ return m_name;
+}
+
+bool
+StdNameInfo::operator == (const NameInfo &info) const
+{
+ return m_name == dynamic_cast<const StdNameInfo&> (info).m_name;
+}
+
+bool
+StdNameInfo::operator < (const NameInfo &info) const
+{
+ return m_name < dynamic_cast<const StdNameInfo&> (info).m_name;
+}
+
+} // Sync
diff --git a/nsync/src/sync-std-name-info.h b/nsync/src/sync-std-name-info.h
new file mode 100644
index 0000000..83bbebb
--- /dev/null
+++ b/nsync/src/sync-std-name-info.h
@@ -0,0 +1,74 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ * Chaoyi Bian <bcy@pku.edu.cn>
+ * Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef SYNC_STD_NAME_INFO_H
+#define SYNC_STD_NAME_INFO_H
+
+#include "sync-name-info.h"
+#include <string>
+
+namespace Sync {
+
+class StdNameInfo : public NameInfo
+{
+public:
+ /**
+ * @brief Lookup existing or create new NameInfo object
+ * @param name routable prefix
+ */
+ static NameInfoConstPtr
+ FindOrCreate (const std::string &name);
+
+ /**
+ * @brief Destructor which will clean up m_names structure
+ */
+ virtual ~StdNameInfo ();
+
+ // from NameInfo
+ virtual bool
+ operator == (const NameInfo &info) const;
+
+ virtual bool
+ operator < (const NameInfo &info) const;
+
+ virtual std::string
+ toString () const;
+
+private:
+ // implementing a singleton pattern.
+ /**
+ * @brief Disabled default constructor. NameInfo object should be created through FindOrCreate static call.
+ */
+
+ /**
+ * @brief Disabled default
+ */
+ StdNameInfo () {}
+ StdNameInfo& operator = (const StdNameInfo &info) { (void)info; return *this; }
+ StdNameInfo (const std::string &name);
+
+ std::string m_name;
+};
+
+} // Sync
+
+#endif // SYNC_CCNX_NAME_INFO_H