util: Support MustBeFresh processing in InMemoryStorage

Change-Id: I8e8e647d7673e4e0fe8dd1c5025fbc8e5e524c70
Refs: #3274
diff --git a/src/util/in-memory-storage-entry.cpp b/src/util/in-memory-storage-entry.cpp
index ae34ba2..c0f5e59 100644
--- a/src/util/in-memory-storage-entry.cpp
+++ b/src/util/in-memory-storage-entry.cpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /**
- * Copyright (c) 2013-2014 Regents of the University of California.
+ * Copyright (c) 2013-2016 Regents of the University of California.
  *
  * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
  *
@@ -24,16 +24,35 @@
 namespace ndn {
 namespace util {
 
+InMemoryStorageEntry::InMemoryStorageEntry()
+  : m_isFresh(true)
+{
+}
+
 void
 InMemoryStorageEntry::release()
 {
   m_dataPacket.reset();
+  m_markStaleEventId.reset();
 }
 
 void
 InMemoryStorageEntry::setData(const Data& data)
 {
   m_dataPacket = data.shared_from_this();
+  m_isFresh = true;
+}
+
+void
+InMemoryStorageEntry::setMarkStaleEventId(unique_ptr<scheduler::ScopedEventId>&& markStaleEventId)
+{
+  m_markStaleEventId = std::move(markStaleEventId);
+}
+
+void
+InMemoryStorageEntry::markStale()
+{
+  m_isFresh = false;
 }
 
 } // namespace util
diff --git a/src/util/in-memory-storage-entry.hpp b/src/util/in-memory-storage-entry.hpp
index 8950b01..6e77b3d 100644
--- a/src/util/in-memory-storage-entry.hpp
+++ b/src/util/in-memory-storage-entry.hpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /**
- * Copyright (c) 2013-2014 Regents of the University of California.
+ * Copyright (c) 2013-2016 Regents of the University of California.
  *
  * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
  *
@@ -25,6 +25,7 @@
 #include "../common.hpp"
 #include "../interest.hpp"
 #include "../data.hpp"
+#include "scheduler-scoped-event-id.hpp"
 
 namespace ndn {
 namespace util {
@@ -34,6 +35,11 @@
 class InMemoryStorageEntry : noncopyable
 {
 public:
+
+  /** @brief Create an entry
+   */
+  InMemoryStorageEntry();
+
   /** @brief Releases reference counts on shared objects
    */
   void
@@ -67,12 +73,35 @@
 
 
   /** @brief Changes the content of in-memory storage entry
+   *
+   *  This method also allows data to satisfy Interest with MustBeFresh
    */
   void
   setData(const Data& data);
 
+  /** @brief Set eventId for the markStale event.
+   */
+  void
+  setMarkStaleEventId(unique_ptr<scheduler::ScopedEventId>&& eventId);
+
+  /** @brief Disable the data from satisfying interest with MustBeFresh
+   */
+  void
+  markStale();
+
+  /** @brief Check if the data can satisfy an interest with MustBeFresh
+   */
+  bool
+  isFresh()
+  {
+    return m_isFresh;
+  }
+
 private:
   shared_ptr<const Data> m_dataPacket;
+
+  bool m_isFresh;
+  unique_ptr<scheduler::ScopedEventId> m_markStaleEventId;
 };
 
 } // namespace util
diff --git a/src/util/in-memory-storage-fifo.cpp b/src/util/in-memory-storage-fifo.cpp
index 91cc7b4..5906d97 100644
--- a/src/util/in-memory-storage-fifo.cpp
+++ b/src/util/in-memory-storage-fifo.cpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /**
- * Copyright (c) 2013-2014 Regents of the University of California.
+ * Copyright (c) 2013-2016 Regents of the University of California.
  *
  * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
  *
@@ -29,6 +29,11 @@
 {
 }
 
+InMemoryStorageFifo::InMemoryStorageFifo(boost::asio::io_service& ioService, size_t limit)
+  : InMemoryStorage(ioService, limit)
+{
+}
+
 InMemoryStorageFifo::~InMemoryStorageFifo()
 {
 }
diff --git a/src/util/in-memory-storage-fifo.hpp b/src/util/in-memory-storage-fifo.hpp
index fc83fe5..4d522a4 100644
--- a/src/util/in-memory-storage-fifo.hpp
+++ b/src/util/in-memory-storage-fifo.hpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /**
- * Copyright (c) 2013-2014 Regents of the University of California.
+ * Copyright (c) 2013-2016 Regents of the University of California.
  *
  * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
  *
@@ -40,6 +40,9 @@
   explicit
   InMemoryStorageFifo(size_t limit = 10);
 
+  explicit
+  InMemoryStorageFifo(boost::asio::io_service& ioService, size_t limit = 10);
+
   virtual
   ~InMemoryStorageFifo();
 
diff --git a/src/util/in-memory-storage-lfu.cpp b/src/util/in-memory-storage-lfu.cpp
index 0596145..0450c6c 100644
--- a/src/util/in-memory-storage-lfu.cpp
+++ b/src/util/in-memory-storage-lfu.cpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /**
- * Copyright (c) 2013-2014 Regents of the University of California.
+ * Copyright (c) 2013-2016 Regents of the University of California.
  *
  * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
  *
@@ -29,6 +29,11 @@
 {
 }
 
+InMemoryStorageLfu::InMemoryStorageLfu(boost::asio::io_service& ioService, size_t limit)
+  : InMemoryStorage(ioService, limit)
+{
+}
+
 InMemoryStorageLfu::~InMemoryStorageLfu()
 {
 }
diff --git a/src/util/in-memory-storage-lfu.hpp b/src/util/in-memory-storage-lfu.hpp
index ac8a02d..f02079e 100644
--- a/src/util/in-memory-storage-lfu.hpp
+++ b/src/util/in-memory-storage-lfu.hpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /**
- * Copyright (c) 2013-2014 Regents of the University of California.
+ * Copyright (c) 2013-2016 Regents of the University of California.
  *
  * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
  *
@@ -43,6 +43,9 @@
   explicit
   InMemoryStorageLfu(size_t limit = 10);
 
+  explicit
+  InMemoryStorageLfu(boost::asio::io_service& ioService, size_t limit = 10);
+
   virtual
   ~InMemoryStorageLfu();
 
diff --git a/src/util/in-memory-storage-lru.cpp b/src/util/in-memory-storage-lru.cpp
index b823b2b..2a50644 100644
--- a/src/util/in-memory-storage-lru.cpp
+++ b/src/util/in-memory-storage-lru.cpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /**
- * Copyright (c) 2013-2014 Regents of the University of California.
+ * Copyright (c) 2013-2016 Regents of the University of California.
  *
  * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
  *
@@ -29,6 +29,12 @@
 {
 }
 
+InMemoryStorageLru::InMemoryStorageLru(boost::asio::io_service& ioService,
+                                       size_t limit)
+  : InMemoryStorage(ioService, limit)
+{
+}
+
 InMemoryStorageLru::~InMemoryStorageLru()
 {
 }
diff --git a/src/util/in-memory-storage-lru.hpp b/src/util/in-memory-storage-lru.hpp
index bde0de4..8d7f852 100644
--- a/src/util/in-memory-storage-lru.hpp
+++ b/src/util/in-memory-storage-lru.hpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /**
- * Copyright (c) 2013-2014 Regents of the University of California.
+ * Copyright (c) 2013-2016 Regents of the University of California.
  *
  * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
  *
@@ -42,6 +42,8 @@
   explicit
   InMemoryStorageLru(size_t limit = 10);
 
+  InMemoryStorageLru(boost::asio::io_service& ioService, size_t limit = 10);
+
   virtual
   ~InMemoryStorageLru();
 
diff --git a/src/util/in-memory-storage-persistent.cpp b/src/util/in-memory-storage-persistent.cpp
index 687a91f..613aa7b 100644
--- a/src/util/in-memory-storage-persistent.cpp
+++ b/src/util/in-memory-storage-persistent.cpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /**
- * Copyright (c) 2013-2014 Regents of the University of California.
+ * Copyright (c) 2013-2016 Regents of the University of California.
  *
  * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
  *
@@ -29,6 +29,11 @@
 {
 }
 
+InMemoryStoragePersistent::InMemoryStoragePersistent(boost::asio::io_service& ioService)
+  : InMemoryStorage(ioService)
+{
+}
+
 InMemoryStoragePersistent::~InMemoryStoragePersistent()
 {
 }
diff --git a/src/util/in-memory-storage-persistent.hpp b/src/util/in-memory-storage-persistent.hpp
index cd9faa3..3cd12ef 100644
--- a/src/util/in-memory-storage-persistent.hpp
+++ b/src/util/in-memory-storage-persistent.hpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /**
- * Copyright (c) 2013-2014 Regents of the University of California.
+ * Copyright (c) 2013-2016 Regents of the University of California.
  *
  * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
  *
@@ -33,9 +33,11 @@
 class InMemoryStoragePersistent : public InMemoryStorage
 {
 public:
-  explicit
   InMemoryStoragePersistent();
 
+  explicit
+  InMemoryStoragePersistent(boost::asio::io_service& ioService);
+
   virtual
   ~InMemoryStoragePersistent();
 
diff --git a/src/util/in-memory-storage.cpp b/src/util/in-memory-storage.cpp
index 4a19660..7d3584c 100644
--- a/src/util/in-memory-storage.cpp
+++ b/src/util/in-memory-storage.cpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /**
- * Copyright (c) 2013-2015 Regents of the University of California.
+ * Copyright (c) 2013-2016 Regents of the University of California.
  *
  * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
  *
@@ -21,6 +21,7 @@
 
 #include "in-memory-storage.hpp"
 #include "in-memory-storage-entry.hpp"
+#include "util/backports.hpp"
 
 #include "crypto.hpp"
 
@@ -29,6 +30,9 @@
 namespace ndn {
 namespace util {
 
+const time::milliseconds InMemoryStorage::INFINITE_WINDOW(-1);
+const time::milliseconds InMemoryStorage::ZERO_WINDOW(0);
+
 InMemoryStorage::const_iterator::const_iterator(const Data* ptr, const Cache* cache,
                                                 Cache::index<byFullName>::type::iterator it)
   : m_ptr(ptr)
@@ -87,10 +91,24 @@
   : m_limit(limit)
   , m_nPackets(0)
 {
+  init();
+}
+
+InMemoryStorage::InMemoryStorage(boost::asio::io_service& ioService, size_t limit)
+  : m_limit(limit)
+  , m_nPackets(0)
+{
+  m_scheduler = make_unique<Scheduler>(ioService);
+  init();
+}
+
+void
+InMemoryStorage::init()
+{
   // TODO consider a more suitable initial value
   m_capacity = 10;
 
-  if (limit != std::numeric_limits<size_t>::max() && m_capacity > m_limit) {
+  if (m_limit != std::numeric_limits<size_t>::max() && m_capacity > m_limit) {
     m_capacity = m_limit;
   }
 
@@ -146,7 +164,7 @@
 }
 
 void
-InMemoryStorage::insert(const Data& data)
+InMemoryStorage::insert(const Data& data, const time::milliseconds& mustBeFreshProcessingWindow)
 {
   //check if identical Data/Name already exists
   Cache::index<byFullName>::type::iterator it = m_cache.get<byFullName>().find(data.getFullName());
@@ -173,6 +191,12 @@
   m_freeEntries.pop();
   m_nPackets++;
   entry->setData(data);
+  if (m_scheduler != nullptr && mustBeFreshProcessingWindow > ZERO_WINDOW) {
+    auto eventId = make_unique<scheduler::ScopedEventId>(*m_scheduler);
+    *eventId = m_scheduler->scheduleEvent(mustBeFreshProcessingWindow,
+                                          bind(&InMemoryStorageEntry::markStale, entry));
+    entry->setMarkStaleEventId(std::move(eventId));
+  }
   m_cache.insert(entry);
 
   //let derived class do something with the entry
@@ -218,7 +242,6 @@
     return shared_ptr<const Data>();
   }
 
-
   //to locate the element that has a just smaller name than the interest's
   if (it != m_cache.get<byFullName>().begin())
     it--;
@@ -234,6 +257,17 @@
   }
 }
 
+InMemoryStorage::Cache::index<InMemoryStorage::byFullName>::type::iterator
+InMemoryStorage::findNextFresh(Cache::index<byFullName>::type::iterator it) const
+{
+  for (; it != m_cache.get<byFullName>().end(); it++) {
+    if ((*it)->isFresh())
+      return it;
+  }
+
+  return it;
+}
+
 InMemoryStorageEntry*
 InMemoryStorage::selectChild(const Interest& interest,
                              Cache::index<byFullName>::type::iterator startingPoint) const
@@ -248,6 +282,14 @@
   bool hasLeftmostSelector = (interest.getChildSelector() <= 0);
   bool hasRightmostSelector = !hasLeftmostSelector;
 
+  // filter out "stale" data
+  if (interest.getMustBeFresh())
+    startingPoint = findNextFresh(startingPoint);
+
+  if (startingPoint == m_cache.get<byFullName>().end()) {
+    return nullptr;
+  }
+
   if (hasLeftmostSelector)
     {
       if (interest.matchesData((*startingPoint)->getData()))
@@ -266,6 +308,9 @@
       while (true)
         {
           ++rightmostCandidate;
+          // filter out "stale" data
+          if (interest.getMustBeFresh())
+            rightmostCandidate = findNextFresh(rightmostCandidate);
 
           bool isInBoundaries = (rightmostCandidate != m_cache.get<byFullName>().end());
           bool isInPrefix = false;
diff --git a/src/util/in-memory-storage.hpp b/src/util/in-memory-storage.hpp
index 5e800c2..bdc3962 100644
--- a/src/util/in-memory-storage.hpp
+++ b/src/util/in-memory-storage.hpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /**
- * Copyright (c) 2013-2014 Regents of the University of California.
+ * Copyright (c) 2013-2016 Regents of the University of California.
  *
  * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
  *
@@ -25,7 +25,7 @@
 #include "../common.hpp"
 #include "../interest.hpp"
 #include "../data.hpp"
-
+#include "scheduler.hpp"
 #include "in-memory-storage-entry.hpp"
 
 #include <boost/multi_index/member.hpp>
@@ -109,9 +109,19 @@
     }
   };
 
+  /** @brief Create a InMemoryStorage with up to @p limit entries
+   *  The InMemoryStorage created through this method will ignore MustBeFresh in interest processing
+   */
   explicit
   InMemoryStorage(size_t limit = std::numeric_limits<size_t>::max());
 
+  /** @brief Create a InMemoryStorage with up to @p limit entries
+   *  The InMemoryStorage created through this method will handle MustBeFresh in interest processing
+   */
+  explicit
+  InMemoryStorage(boost::asio::io_service& ioService,
+                  size_t limit = std::numeric_limits<size_t>::max());
+
   /** @note Please make sure to implement it to free m_freeEntries and evict
     * all items in the derived class for anybody who wishes to inherit this class
     */
@@ -120,6 +130,10 @@
 
   /** @brief Inserts a Data packet
    *
+   *  @param data the packet to insert
+   *  @param mustBeFreshProcessingWindow Beyond this time period after the data is inserted, the
+   *         data can only be used to answer interest without MustBeFresh selector.
+   *
    *  @note Packets are considered duplicate if the name with implicit digest matches.
    *  The new Data packet with the identical name, but a different payload
    *  will be placed in the in-memory storage.
@@ -127,7 +141,7 @@
    *  @note It will invoke afterInsert(shared_ptr<InMemoryStorageEntry>).
    */
   void
-  insert(const Data& data);
+  insert(const Data& data, const time::milliseconds& mustBeFreshProcessingWindow = INFINITE_WINDOW);
 
   /** @brief Finds the best match Data for an Interest
    *
@@ -294,6 +308,24 @@
   selectChild(const Interest& interest,
               Cache::index<byFullName>::type::iterator startingPoint) const;
 
+  /** @brief Get the next iterator (include startingPoint) that satisfies MustBeFresh requirement
+   *
+   *  @param startingPoint The iterator to start with.
+   *  @return The next qualified iterator
+   */
+  Cache::index<byFullName>::type::iterator
+  findNextFresh(Cache::index<byFullName>::type::iterator startingPoint) const;
+
+private:
+  void
+  init();
+
+public:
+  static const time::milliseconds INFINITE_WINDOW;
+
+private:
+  static const time::milliseconds ZERO_WINDOW;
+
 private:
   Cache m_cache;
   /// user defined maximum capacity of the in-memory storage in packets
@@ -304,6 +336,8 @@
   size_t m_nPackets;
   /// memory pool
   std::stack<InMemoryStorageEntry*> m_freeEntries;
+  /// scheduler
+  unique_ptr<Scheduler> m_scheduler;
 };
 
 } // namespace util
diff --git a/tests/unit-tests/util/test-in-memory-storage-common.cpp b/tests/unit-tests/util/test-in-memory-storage-common.cpp
index f2c1b9f..ea78f29 100644
--- a/tests/unit-tests/util/test-in-memory-storage-common.cpp
+++ b/tests/unit-tests/util/test-in-memory-storage-common.cpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /**
- * Copyright (c) 2013-2015 Regents of the University of California.
+ * Copyright (c) 2013-2016 Regents of the University of California.
  *
  * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
  *
@@ -27,6 +27,7 @@
 
 #include "boost-test.hpp"
 #include "../make-interest-data.hpp"
+#include "../unit-test-time-fixture.hpp"
 
 #include <boost/mpl/list.hpp>
 
@@ -631,7 +632,7 @@
 typedef boost::mpl::list<InMemoryStorageFifo, InMemoryStorageLfu, InMemoryStorageLru>
                          InMemoryStoragesLimited;
 
-BOOST_AUTO_TEST_CASE_TEMPLATE(setCapacity, T, InMemoryStoragesLimited)
+BOOST_AUTO_TEST_CASE_TEMPLATE(SetCapacity, T, InMemoryStoragesLimited)
 {
   T ims;
 
@@ -700,18 +701,24 @@
 
 ///as Find function is implemented at the base case, therefore testing for one derived class is
 ///sufficient for all
-class FindFixture
+class FindFixture : public ndn::tests::UnitTestTimeFixture
 {
 protected:
+  FindFixture()
+    : m_ims(io)
+  {
+  }
+
   Name
-  insert(uint32_t id, const Name& name)
+  insert(uint32_t id, const Name& name,
+         const time::milliseconds& freshWindow = InMemoryStorage::INFINITE_WINDOW)
   {
     shared_ptr<Data> data = makeData(name);
     data->setFreshnessPeriod(time::milliseconds(99999));
     data->setContent(reinterpret_cast<const uint8_t*>(&id), sizeof(id));
     signData(data);
 
-    m_ims.insert(*data);
+    m_ims.insert(*data, freshWindow);
 
     return data->getFullName();
   }
@@ -975,6 +982,78 @@
   BOOST_CHECK_EQUAL(find(), 1);
 }
 
+BOOST_AUTO_TEST_CASE(MustBeFresh)
+{
+  Name data1Name = insert(1, "ndn:/A/1", time::milliseconds(500));
+  insert(2, "ndn:/A/2", time::milliseconds(2500));
+  insert(3, "ndn:/A/3", time::milliseconds(3500));
+  insert(4, "ndn:/A/4", time::milliseconds(1500));
+
+  // @0s, all Data are fresh
+  startInterest("ndn:/A/1")
+    .setMustBeFresh(true);
+  BOOST_CHECK_EQUAL(find(), 1);
+
+  startInterest("ndn:/A/1")
+    .setMustBeFresh(false);
+  BOOST_CHECK_EQUAL(find(), 1);
+
+  startInterest("ndn:/A")
+    .setMustBeFresh(true)
+    .setChildSelector(0);
+  BOOST_CHECK_EQUAL(find(), 1);
+
+  startInterest("ndn:/A")
+    .setMustBeFresh(true)
+    .setChildSelector(1);
+  BOOST_CHECK_EQUAL(find(), 4);
+
+  advanceClocks(time::milliseconds(1000));
+  // @1s, /A/1 is stale
+  startInterest("ndn:/A/1")
+    .setMustBeFresh(true);
+  BOOST_CHECK_EQUAL(find(), 0);
+  startInterest("ndn:/A/1")
+    .setMustBeFresh(false);
+  BOOST_CHECK_EQUAL(find(), 1);
+
+  // MustBeFresh is ignored when full Name is specified
+  startInterest(data1Name)
+    .setMustBeFresh(true);
+  BOOST_CHECK_EQUAL(find(), 1);
+
+  startInterest("ndn:/A")
+    .setMustBeFresh(true)
+    .setChildSelector(0);
+  BOOST_CHECK_EQUAL(find(), 2);
+  startInterest("ndn:/A")
+    .setMustBeFresh(false)
+    .setChildSelector(0);
+  BOOST_CHECK_EQUAL(find(), 1);
+
+  advanceClocks(time::milliseconds(1000));
+  // @2s, /A/1 and /A/4 are stale
+  startInterest("ndn:/A")
+    .setMustBeFresh(true)
+    .setChildSelector(1);
+  BOOST_CHECK_EQUAL(find(), 3);
+  startInterest("ndn:/A")
+    .setMustBeFresh(false)
+    .setChildSelector(1);
+  BOOST_CHECK_EQUAL(find(), 4);
+
+  advanceClocks(time::milliseconds(2000));
+  // @4s, all Data are stale
+  startInterest("ndn:/A")
+    .setMustBeFresh(true)
+    .setChildSelector(0);
+  BOOST_CHECK_EQUAL(find(), 0);
+  startInterest("ndn:/A")
+    .setMustBeFresh(true)
+    .setChildSelector(1);
+  BOOST_CHECK_EQUAL(find(), 0);
+}
+
 BOOST_AUTO_TEST_SUITE_END() // Find
 BOOST_AUTO_TEST_SUITE_END() // Common
 BOOST_AUTO_TEST_SUITE_END() // UtilInMemoryStorage