util: Importing scheduler, originally implemented in NFD

The scheduler uses monotonic clock whenever available.

This commit also includes an example to show how to work with the
scheduler.

Change-Id: I006bcc6afddd33caa8d1ec9575c0596234315411
diff --git a/examples/consumer-with-timer.cpp b/examples/consumer-with-timer.cpp
new file mode 100644
index 0000000..b8415d0
--- /dev/null
+++ b/examples/consumer-with-timer.cpp
@@ -0,0 +1,98 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/**
+ * Copyright (C) 2013 Regents of the University of California.
+ * @author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ * See COPYING for copyright and distribution information.
+ */
+
+// correct way to include NDN-CPP headers
+// #include <ndn-cpp-dev/face.hpp>
+#include "face.hpp"
+#include "util/scheduler.hpp"
+
+#include <stdexcept>
+
+#if NDN_CPP_HAVE_CXX11
+// In the std library, the placeholders are in a different namespace than boost.
+using namespace ndn::func_lib::placeholders;
+#endif
+
+void
+onData(ndn::Face &face,
+       const ndn::ptr_lib::shared_ptr<const ndn::Interest> &interest, const ndn::ptr_lib::shared_ptr<ndn::Data> &data)
+{
+  std::cout << "I: " << interest->toUri() << std::endl;
+  std::cout << "D: " << data->getName().toUri() << std::endl;
+}
+
+void
+onTimeout(ndn::Face &face,
+          const ndn::ptr_lib::shared_ptr<const ndn::Interest> &interest)
+{
+  std::cout << "Timeout" << std::endl;
+}
+
+void
+delayedInterest(ndn::Face &face)
+{
+  std::cout << "One more Interest, delayed by the scheduler" << std::endl;
+  
+  ndn::Interest i(ndn::Name("/localhost/testApp/randomData"));
+  i.setScope(1);
+  i.setInterestLifetime(1000);
+  i.setMustBeFresh(true);
+
+  face.expressInterest(i,
+                       ndn::bind(&onData, boost::ref(face), _1, _2),
+                       ndn::bind(&onTimeout, boost::ref(face), _1));
+}
+
+void
+BlockPrinter(const ndn::Block &block, const std::string &indent="")
+{
+  std::cout << indent << block.type() << " (" << block.value_size() << ") [[";
+  std::cout.write(reinterpret_cast<const char *>(block.value()), block.value_size());
+  std::cout<< "]]" << std::endl;
+
+  for(ndn::Block::element_const_iterator i = block.getAll().begin();
+      i != block.getAll().end();
+      ++i)
+    {
+      BlockPrinter(*i, indent+"  ");
+    }
+}
+
+int main()
+{
+  try {
+    // Explicitly create io_service object, which can be shared between
+    // Face and Scheduler
+    ndn::shared_ptr<boost::asio::io_service> io =
+      ndn::make_shared<boost::asio::io_service>();
+    
+    ndn::Interest i(ndn::Name("/localhost/testApp/randomData"));
+    i.setScope(1);
+    i.setInterestLifetime(1000);
+    i.setMustBeFresh(true);
+
+    ndn::Face face(io);
+    face.expressInterest(i,
+                          ndn::bind(&onData, boost::ref(face), _1, _2),
+                          ndn::bind(&onTimeout, boost::ref(face), _1));
+
+
+    ndn::Scheduler scheduler(*io);
+    scheduler.scheduleEvent(ndn::time::seconds(2),
+                            ndn::bind(&delayedInterest, boost::ref(face)));
+    
+    io->run();
+    
+    // Alternatively, a helper face.processEvents() also can be called
+    // processEvents will block until the requested data received or timeout occurs
+    // face.processEvents();
+  }
+  catch(std::exception &e) {
+    std::cerr << "ERROR: " << e.what() << std::endl;
+  }
+  return 0;
+}
diff --git a/src/util/monotonic_deadline_timer.hpp b/src/util/monotonic_deadline_timer.hpp
new file mode 100644
index 0000000..3cfb05f
--- /dev/null
+++ b/src/util/monotonic_deadline_timer.hpp
@@ -0,0 +1,62 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (C) 2014 Named Data Networking Project
+ * See COPYING for copyright and distribution information.
+ */
+
+/**
+ * This code is based on https://svn.boost.org/trac/boost/attachment/ticket/3504/MonotonicDeadlineTimer.h
+ */
+
+#ifndef NDN_UTIL_MONOTONIC_DEADLINE_TIMER_HPP
+#define NDN_UTIL_MONOTONIC_DEADLINE_TIMER_HPP
+
+#include <boost/asio.hpp>
+#include "time.hpp"
+
+namespace boost {
+namespace asio {
+
+template <> 
+struct time_traits<ndn::time::monotonic_clock>
+{
+  typedef ndn::time::Point time_type;
+  typedef ndn::time::Duration duration_type;
+
+  static time_type
+  now()
+  {
+    return ndn::time::now();
+  }
+
+  static time_type
+  add(const time_type& time, const duration_type& duration) 
+  {
+    return time + duration;
+  }
+
+  static duration_type
+  subtract(const time_type& timeLhs, const time_type& timeRhs)
+  {
+    return timeLhs - timeRhs;
+  }
+
+  static bool
+  less_than(const time_type& timeLhs, const time_type& timeRhs)
+  {
+    return timeLhs < timeRhs;
+  }
+
+  static boost::posix_time::time_duration
+  to_posix_duration(const duration_type& duration)
+  {
+    return boost::posix_time::microseconds(duration/1000);
+  }
+};
+
+typedef basic_deadline_timer<ndn::time::monotonic_clock> monotonic_deadline_timer; 
+
+} // namespace asio
+} // namespace boost
+
+#endif // NDN_UTIL_MONOTONIC_DEADLINE_TIMER_HPP
diff --git a/src/util/scheduler.cpp b/src/util/scheduler.cpp
new file mode 100644
index 0000000..c4fc1d8
--- /dev/null
+++ b/src/util/scheduler.cpp
@@ -0,0 +1,176 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (C) 2014 Named Data Networking Project
+ * See COPYING for copyright and distribution information.
+ */
+
+#include "scheduler.hpp"
+
+namespace ndn {
+
+struct EventIdImpl
+{
+  EventIdImpl(const Scheduler::EventQueue::iterator& event)
+    : m_event(event)
+    , m_isValid(true)
+  {
+  }
+
+  void
+  invalidate()
+  {
+    m_isValid = false;
+  }
+
+  bool
+  isValid() const
+  {
+    return m_isValid;
+  }
+
+  operator const Scheduler::EventQueue::iterator&() const
+  {
+    return m_event;
+  }
+
+  void
+  reset(const Scheduler::EventQueue::iterator& newIterator)
+  {
+    m_event = newIterator;
+    m_isValid = true;
+  }
+
+private:
+  Scheduler::EventQueue::iterator m_event;
+  bool m_isValid;
+};
+
+Scheduler::EventInfo::EventInfo(const time::Duration& after,
+                        const time::Duration& period,
+                        const Event& event)
+  : m_scheduledTime(time::now() + after)
+  , m_period(period)
+  , m_event(event)
+{
+}
+
+Scheduler::EventInfo::EventInfo(const time::Point& when, const EventInfo& previousEvent)
+  : m_scheduledTime(when)
+  , m_period(previousEvent.m_period)
+  , m_event(previousEvent.m_event)
+  , m_eventId(previousEvent.m_eventId)
+{
+}
+
+time::Duration
+Scheduler::EventInfo::expiresFromNow() const
+{
+  time::Point now = time::now();
+  if (now > m_scheduledTime)
+    return time::seconds(0); // event should be scheduled ASAP
+  else
+    return m_scheduledTime - now;
+}
+
+
+Scheduler::Scheduler(boost::asio::io_service& ioService)
+  : m_ioService(ioService)
+  , m_scheduledEvent(m_events.end())
+  , m_deadlineTimer(ioService)
+{
+}
+
+EventId
+Scheduler::scheduleEvent(const time::Duration& after,
+                         const Event& event)
+{
+  return schedulePeriodicEvent(after, time::nanoseconds(-1), event);
+}
+
+EventId
+Scheduler::schedulePeriodicEvent(const time::Duration& after,
+                                 const time::Duration& period,
+                                 const Event& event)
+{
+  EventQueue::iterator i = m_events.insert(EventInfo(after, period, event));
+  i->m_eventId = make_shared<EventIdImpl>(boost::cref(i));
+  
+  if (m_scheduledEvent == m_events.end() ||
+      *i < *m_scheduledEvent)
+    {
+      m_deadlineTimer.expires_from_now(after);
+      m_deadlineTimer.async_wait(bind(&Scheduler::onEvent, this, _1));
+      m_scheduledEvent = i;
+    }
+
+  return i->m_eventId;
+}
+  
+void
+Scheduler::cancelEvent(const EventId& eventId)
+{
+  if (!eventId->isValid())
+    return; // event already fired or cancelled
+  
+  if (static_cast<EventQueue::iterator>(*eventId) != m_scheduledEvent) {
+    m_events.erase(*eventId);
+    eventId->invalidate();
+    return;
+  }
+  
+  m_deadlineTimer.cancel();
+  m_events.erase(static_cast<EventQueue::iterator>(*eventId));
+  eventId->invalidate();
+
+  if (!m_events.empty())
+    {
+      m_deadlineTimer.expires_from_now(m_events.begin()->expiresFromNow());
+      m_deadlineTimer.async_wait(bind(&Scheduler::onEvent, this, _1));
+      m_scheduledEvent = m_events.begin();
+    }
+  else
+    {
+      m_deadlineTimer.cancel();
+      m_scheduledEvent = m_events.end();
+    }
+}
+
+void
+Scheduler::onEvent(const boost::system::error_code& error)
+{
+  if (error) // e.g., cancelled
+    {
+      return;
+    }
+  
+  // process all expired events
+  time::Point now = time::now();
+  while(!m_events.empty() && m_events.begin()->m_scheduledTime <= now)
+    {
+      EventQueue::iterator head = m_events.begin();
+      
+      head->m_event();
+      if (head->m_period < 0)
+        {
+          head->m_eventId->invalidate();
+          m_events.erase(head);
+        }
+      else
+        {
+          // "reschedule" and update EventId data of the event
+          EventInfo event(now + head->m_period, *head);
+          EventQueue::iterator i = m_events.insert(event);
+          i->m_eventId->reset(i);
+          m_events.erase(head);
+        }
+    }
+
+  if (!m_events.empty())
+    {
+      m_deadlineTimer.expires_from_now(m_events.begin()->m_scheduledTime - now);
+      m_deadlineTimer.async_wait(bind(&Scheduler::onEvent, this, _1));
+    }
+}
+
+
+} // namespace ndn
diff --git a/src/util/scheduler.hpp b/src/util/scheduler.hpp
new file mode 100644
index 0000000..b1fb596
--- /dev/null
+++ b/src/util/scheduler.hpp
@@ -0,0 +1,99 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (C) 2014 Named Data Networking Project
+ * See COPYING for copyright and distribution information.
+ */
+
+#ifndef NDN_UTIL_SCHEDULER_HPP
+#define NDN_UTIL_SCHEDULER_HPP
+
+#include "../common.hpp"
+#include "monotonic_deadline_timer.hpp"
+
+namespace ndn {
+
+struct EventIdImpl; ///< \brief Private storage of information about the event
+/**
+ * \brief Opaque type (shared_ptr) representing ID of the scheduled event
+ */
+typedef shared_ptr<EventIdImpl> EventId;
+
+/**
+ * \brief Generic scheduler
+ */
+class Scheduler
+{
+public:
+  typedef function<void()> Event;
+
+  Scheduler(boost::asio::io_service& ioService);
+
+  /**
+   * \brief Schedule one time event after the specified delay
+   * \returns EventId that can be used to cancel the scheduled event
+   */
+  EventId
+  scheduleEvent(const time::Duration& after, const Event& event);
+
+  /**
+   * \brief Schedule periodic event that should be fired every specified period.
+   *        First event will be fired after the specified delay.
+   * \returns EventId that can be used to cancel the scheduled event
+   */
+  EventId
+  schedulePeriodicEvent(const time::Duration& after,
+                        const time::Duration& period,
+                        const Event& event);
+  
+  /**
+   * \brief Cancel scheduled event
+   */
+  void
+  cancelEvent(const EventId& eventId);
+
+private:
+  void
+  onEvent(const boost::system::error_code& code);
+  
+private:
+  boost::asio::io_service& m_ioService;
+
+  struct EventInfo
+  {
+    EventInfo(const time::Duration& after,
+              const time::Duration& period,
+              const Event& event);
+    EventInfo(const time::Point& when, const EventInfo& previousEvent);
+
+    bool
+    operator <=(const EventInfo& other) const
+    {
+      return this->m_scheduledTime <= other.m_scheduledTime;
+    }
+
+    bool
+    operator <(const EventInfo& other) const
+    {
+      return this->m_scheduledTime < other.m_scheduledTime;
+    }
+
+    time::Duration
+    expiresFromNow() const;
+    
+    time::Point m_scheduledTime;
+    time::Duration m_period;
+    Event m_event;
+    mutable EventId m_eventId;
+  };
+
+  typedef std::multiset<EventInfo> EventQueue;
+  friend struct EventIdImpl;
+
+  EventQueue m_events;
+  EventQueue::iterator m_scheduledEvent;
+  boost::asio::monotonic_deadline_timer m_deadlineTimer;
+};
+
+} // namespace ndn
+
+#endif // NDN_UTIL_SCHEDULER_HPP
diff --git a/src/util/time.cpp b/src/util/time.cpp
new file mode 100644
index 0000000..97ac14c
--- /dev/null
+++ b/src/util/time.cpp
@@ -0,0 +1,47 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (C) 2014 Named Data Networking Project
+ * See COPYING for copyright and distribution information.
+ */
+
+#include "time.hpp"
+#include <time.h>
+#include <stdexcept>
+#include <sys/time.h>
+
+namespace ndn {
+namespace time {
+
+Point
+now()
+{
+// based on suggestion from https://svn.boost.org/trac/boost/ticket/3504
+#if defined(_POSIX_TIMERS) && ( _POSIX_TIMERS > 0 ) && defined(_POSIX_MONOTONIC_CLOCK)
+
+  struct timespec t;
+  int res = clock_gettime(CLOCK_MONOTONIC, &t);
+
+  if (res == -1) {
+    throw std::runtime_error("clock_gettime");
+  }
+
+  return Point(time::seconds(t.tv_sec) + time::nanoseconds(t.tv_nsec));
+
+#else
+
+  // fallback to wall clock time
+
+  struct timeval tv;
+  int res = gettimeofday(&tv, 0);
+
+  if (res == -1) {
+    throw std::runtime_error("gettimeofday");
+  }
+
+  return Point(time::seconds(tv.tv_sec) + time::microseconds(tv.tv_usec));
+
+#endif
+}
+
+} // namespace time
+} // namespace ndn
diff --git a/src/util/time.hpp b/src/util/time.hpp
index 82d59e9..d175964 100644
--- a/src/util/time.hpp
+++ b/src/util/time.hpp
@@ -62,6 +62,153 @@
   return (boostTime-UNIX_EPOCH_TIME).total_milliseconds();
 }
 
+namespace time {
+
+class monotonic_clock;
+
+/** \class Duration
+ *  \brief represents a time interval
+ *  Time unit is nanosecond.
+ */
+class Duration
+{
+public:
+  Duration()
+    : m_value(0)
+  {
+  }
+
+  explicit
+  Duration(int64_t value)
+    : m_value(value)
+  {
+  }
+  
+  operator int64_t&()
+  {
+    return m_value;
+  }
+
+  operator const int64_t&() const
+  {
+    return m_value;
+  }
+
+  Duration
+  operator+(const Duration& other) const
+  {
+    return Duration(this->m_value + other.m_value);
+  }
+  
+  Duration
+  operator-(const Duration& other) const
+  {
+    return Duration(this->m_value - other.m_value);
+  }
+
+private:
+  int64_t m_value;
+};
+
+/** \class Point
+ *  \brief represents a point in time
+ *  This uses monotonic clock.
+ */
+class Point
+{
+public:
+  Point()
+    : m_value(0)
+  {
+  }
+
+  explicit
+  Point(int64_t value)
+    : m_value(value)
+  {
+  }
+  
+  operator int64_t&()
+  {
+    return m_value;
+  }
+
+  operator const int64_t&() const
+  {
+    return m_value;
+  }
+
+  Point
+  operator+(const Duration& other) const
+  {
+    return Point(this->m_value + static_cast<int64_t>(other));
+  }
+  
+  Duration
+  operator-(const Point& other) const
+  {
+    return Duration(this->m_value - other.m_value);
+  }
+
+  Point
+  operator-(const Duration& other) const
+  {
+    return Point(this->m_value  - static_cast<int64_t>(other));
+  }
+  
+private:
+  int64_t m_value;
+};
+
+/**
+ * \brief Get current time
+ * \return{ the current time in monotonic clock }
+ */
+Point
+now();
+
+/**
+ * \brief Get time::Duration for the specified number of seconds
+ */
+template<class T>
+inline Duration
+seconds(T value)
+{
+  return Duration(value * static_cast<int64_t>(1000000000));
+}
+
+/**
+ * \brief Get time::Duration for the specified number of milliseconds
+ */
+template<class T>
+inline Duration
+milliseconds(T value)
+{
+  return Duration(value * static_cast<int64_t>(1000000));
+}
+
+/**
+ * \brief Get time::Duration for the specified number of microseconds
+ */
+template<class T>
+inline Duration
+microseconds(T value)
+{
+  return Duration(value * static_cast<int64_t>(1000));
+}
+
+/**
+ * \brief Get time::Duration for the specified number of nanoseconds
+ */
+inline Duration
+nanoseconds(int64_t value)
+{
+  return Duration(value);
+}
+
+
+} // namespace time
+
 } // namespace ndn
 
 #endif // NDN_TIME_HPP
diff --git a/tests/test-scheduler.cpp b/tests/test-scheduler.cpp
new file mode 100644
index 0000000..b63c3c0
--- /dev/null
+++ b/tests/test-scheduler.cpp
@@ -0,0 +1,85 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (C) 2014 Named Data Networking Project
+ * See COPYING for copyright and distribution information.
+ */
+
+#include "util/scheduler.hpp"
+
+#include <boost/test/unit_test.hpp>
+
+namespace ndn {
+
+BOOST_AUTO_TEST_SUITE(TestScheduler)
+
+struct SchedulerFixture
+{
+  SchedulerFixture()
+    : count1(0)
+    , count2(0)
+    , count3(0)
+    , count4(0)
+  {
+  }
+    
+  void
+  event1()
+  {
+    BOOST_CHECK_EQUAL(count3, 1);
+    ++count1;
+  }
+
+  void
+  event2()
+  {
+    ++count2;
+  }
+
+  void
+  event3()
+  {
+    BOOST_CHECK_EQUAL(count1, 0);
+    ++count3;
+  }
+
+  void
+  event4()
+  {
+    ++count4;
+  }
+  
+  int count1;
+  int count2;
+  int count3;
+  int count4;
+};
+
+BOOST_FIXTURE_TEST_CASE(Events, SchedulerFixture)
+{
+  boost::asio::io_service io; 
+
+  Scheduler scheduler(io);
+  scheduler.scheduleEvent(time::seconds(0.1), bind(&SchedulerFixture::event1, this));
+  
+  EventId i = scheduler.scheduleEvent(time::seconds(0.2), bind(&SchedulerFixture::event2, this));
+  scheduler.cancelEvent(i);
+
+  scheduler.scheduleEvent(time::seconds(0.05), bind(&SchedulerFixture::event3, this));
+
+  i = scheduler.scheduleEvent(time::seconds(0.01), bind(&SchedulerFixture::event2, this));
+  scheduler.cancelEvent(i);
+
+  i = scheduler.schedulePeriodicEvent(time::seconds(0.3), time::seconds(0.1), bind(&SchedulerFixture::event4, this));
+  scheduler.scheduleEvent(time::seconds(0.69), bind(&Scheduler::cancelEvent, &scheduler, i));
+  
+  io.run();
+
+  BOOST_CHECK_EQUAL(count1, 1);
+  BOOST_CHECK_EQUAL(count2, 0);
+  BOOST_CHECK_EQUAL(count3, 1);
+  BOOST_CHECK_EQUAL(count4, 4);
+}
+
+BOOST_AUTO_TEST_SUITE_END()
+
+} // namespace ndn