ims: move InMemoryStorage from util/
refs #3940
Change-Id: I4468fe9b65ef6263a62800701eb6b03df28fa274
diff --git a/src/ims/in-memory-storage-entry.cpp b/src/ims/in-memory-storage-entry.cpp
new file mode 100644
index 0000000..daf12c5
--- /dev/null
+++ b/src/ims/in-memory-storage-entry.cpp
@@ -0,0 +1,57 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2013-2017 Regents of the University of California.
+ *
+ * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
+ *
+ * ndn-cxx library is free software: you can redistribute it and/or modify it under the
+ * terms of the GNU Lesser General Public License as published by the Free Software
+ * Foundation, either version 3 of the License, or (at your option) any later version.
+ *
+ * ndn-cxx library 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 Lesser General Public License for more details.
+ *
+ * You should have received copies of the GNU General Public License and GNU Lesser
+ * General Public License along with ndn-cxx, e.g., in COPYING.md file. If not, see
+ * <http://www.gnu.org/licenses/>.
+ *
+ * See AUTHORS.md for complete list of ndn-cxx authors and contributors.
+ */
+
+#include "in-memory-storage-entry.hpp"
+
+namespace ndn {
+
+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<util::scheduler::ScopedEventId> markStaleEventId)
+{
+ m_markStaleEventId = std::move(markStaleEventId);
+}
+
+void
+InMemoryStorageEntry::markStale()
+{
+ m_isFresh = false;
+}
+
+} // namespace ndn
diff --git a/src/ims/in-memory-storage-entry.hpp b/src/ims/in-memory-storage-entry.hpp
new file mode 100644
index 0000000..721a90d
--- /dev/null
+++ b/src/ims/in-memory-storage-entry.hpp
@@ -0,0 +1,104 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2013-2017 Regents of the University of California.
+ *
+ * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
+ *
+ * ndn-cxx library is free software: you can redistribute it and/or modify it under the
+ * terms of the GNU Lesser General Public License as published by the Free Software
+ * Foundation, either version 3 of the License, or (at your option) any later version.
+ *
+ * ndn-cxx library 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 Lesser General Public License for more details.
+ *
+ * You should have received copies of the GNU General Public License and GNU Lesser
+ * General Public License along with ndn-cxx, e.g., in COPYING.md file. If not, see
+ * <http://www.gnu.org/licenses/>.
+ *
+ * See AUTHORS.md for complete list of ndn-cxx authors and contributors.
+ */
+
+#ifndef NDN_IMS_IN_MEMORY_STORAGE_ENTRY_HPP
+#define NDN_IMS_IN_MEMORY_STORAGE_ENTRY_HPP
+
+#include "../data.hpp"
+#include "../interest.hpp"
+#include "../util/scheduler-scoped-event-id.hpp"
+
+namespace ndn {
+
+/** @brief Represents an in-memory storage entry
+ */
+class InMemoryStorageEntry : noncopyable
+{
+public:
+ /** @brief Create an entry
+ */
+ InMemoryStorageEntry();
+
+ /** @brief Releases reference counts on shared objects
+ */
+ void
+ release();
+
+ /** @brief Returns the name of the Data packet stored in the in-memory storage entry
+ */
+ const Name&
+ getName() const
+ {
+ return m_dataPacket->getName();
+ }
+
+ /** @brief Returns the full name (including implicit digest) of the Data packet stored
+ * in the in-memory storage entry
+ */
+ const Name&
+ getFullName() const
+ {
+ return m_dataPacket->getFullName();
+ }
+
+ /** @brief Returns the Data packet stored in the in-memory storage entry
+ */
+ const Data&
+ getData() const
+ {
+ return *m_dataPacket;
+ }
+
+ /** @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<util::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<util::scheduler::ScopedEventId> m_markStaleEventId;
+};
+
+} // namespace ndn
+
+#endif // NDN_IMS_IN_MEMORY_STORAGE_ENTRY_HPP
diff --git a/src/ims/in-memory-storage-fifo.cpp b/src/ims/in-memory-storage-fifo.cpp
new file mode 100644
index 0000000..df6e173
--- /dev/null
+++ b/src/ims/in-memory-storage-fifo.cpp
@@ -0,0 +1,64 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2013-2017 Regents of the University of California.
+ *
+ * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
+ *
+ * ndn-cxx library is free software: you can redistribute it and/or modify it under the
+ * terms of the GNU Lesser General Public License as published by the Free Software
+ * Foundation, either version 3 of the License, or (at your option) any later version.
+ *
+ * ndn-cxx library 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 Lesser General Public License for more details.
+ *
+ * You should have received copies of the GNU General Public License and GNU Lesser
+ * General Public License along with ndn-cxx, e.g., in COPYING.md file. If not, see
+ * <http://www.gnu.org/licenses/>.
+ *
+ * See AUTHORS.md for complete list of ndn-cxx authors and contributors.
+ */
+
+#include "in-memory-storage-fifo.hpp"
+
+namespace ndn {
+
+InMemoryStorageFifo::InMemoryStorageFifo(size_t limit)
+ : InMemoryStorage(limit)
+{
+}
+
+InMemoryStorageFifo::InMemoryStorageFifo(boost::asio::io_service& ioService, size_t limit)
+ : InMemoryStorage(ioService, limit)
+{
+}
+
+void
+InMemoryStorageFifo::afterInsert(InMemoryStorageEntry* entry)
+{
+ BOOST_ASSERT(m_cleanupIndex.size() <= size());
+ m_cleanupIndex.insert(entry);
+}
+
+bool
+InMemoryStorageFifo::evictItem()
+{
+ if (!m_cleanupIndex.get<byArrival>().empty()) {
+ CleanupIndex::index<byArrival>::type::iterator it = m_cleanupIndex.get<byArrival>().begin();
+ eraseImpl((*it)->getFullName());
+ m_cleanupIndex.get<byArrival>().erase(it);
+ return true;
+ }
+
+ return false;
+}
+
+void
+InMemoryStorageFifo::beforeErase(InMemoryStorageEntry* entry)
+{
+ CleanupIndex::index<byEntity>::type::iterator it = m_cleanupIndex.get<byEntity>().find(entry);
+ if (it != m_cleanupIndex.get<byEntity>().end())
+ m_cleanupIndex.get<byEntity>().erase(it);
+}
+
+} // namespace ndn
diff --git a/src/ims/in-memory-storage-fifo.hpp b/src/ims/in-memory-storage-fifo.hpp
new file mode 100644
index 0000000..6991451
--- /dev/null
+++ b/src/ims/in-memory-storage-fifo.hpp
@@ -0,0 +1,90 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2013-2017 Regents of the University of California.
+ *
+ * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
+ *
+ * ndn-cxx library is free software: you can redistribute it and/or modify it under the
+ * terms of the GNU Lesser General Public License as published by the Free Software
+ * Foundation, either version 3 of the License, or (at your option) any later version.
+ *
+ * ndn-cxx library 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 Lesser General Public License for more details.
+ *
+ * You should have received copies of the GNU General Public License and GNU Lesser
+ * General Public License along with ndn-cxx, e.g., in COPYING.md file. If not, see
+ * <http://www.gnu.org/licenses/>.
+ *
+ * See AUTHORS.md for complete list of ndn-cxx authors and contributors.
+ */
+
+#ifndef NDN_IMS_IN_MEMORY_STORAGE_FIFO_HPP
+#define NDN_IMS_IN_MEMORY_STORAGE_FIFO_HPP
+
+#include "in-memory-storage.hpp"
+
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/hashed_index.hpp>
+#include <boost/multi_index/sequenced_index.hpp>
+
+namespace ndn {
+
+/** @brief Provides in-memory storage employing First-In-First-Out (FIFO) replacement policy.
+ */
+class InMemoryStorageFifo : public InMemoryStorage
+{
+public:
+ explicit
+ InMemoryStorageFifo(size_t limit = 10);
+
+ explicit
+ InMemoryStorageFifo(boost::asio::io_service& ioService, size_t limit = 10);
+
+NDN_CXX_PUBLIC_WITH_TESTS_ELSE_PROTECTED:
+ /** @brief Removes one Data packet from in-memory storage based on FIFO
+ * @return{ whether the Data was removed }
+ */
+ bool
+ evictItem() override;
+
+ /** @brief Update the entry after a entry is successfully inserted, add it to the cleanupIndex
+ */
+ void
+ afterInsert(InMemoryStorageEntry* entry) override;
+
+ /** @brief Update the entry or other data structures before a entry is successfully erased,
+ * erase it from the cleanupIndex
+ */
+ void
+ beforeErase(InMemoryStorageEntry* entry) override;
+
+private:
+ // multi_index_container to implement FIFO
+ class byArrival;
+ class byEntity;
+
+ typedef boost::multi_index_container<
+ InMemoryStorageEntry*,
+ boost::multi_index::indexed_by<
+
+ // by Entry itself
+ boost::multi_index::hashed_unique<
+ boost::multi_index::tag<byEntity>,
+ boost::multi_index::identity<InMemoryStorageEntry*>
+ >,
+
+ // by arrival (FIFO)
+ boost::multi_index::sequenced<
+ boost::multi_index::tag<byArrival>
+ >
+
+ >
+ > CleanupIndex;
+
+ CleanupIndex m_cleanupIndex;
+};
+
+} // namespace ndn
+
+#endif // NDN_IMS_IN_MEMORY_STORAGE_FIFO_HPP
diff --git a/src/ims/in-memory-storage-lfu.cpp b/src/ims/in-memory-storage-lfu.cpp
new file mode 100644
index 0000000..a155f60
--- /dev/null
+++ b/src/ims/in-memory-storage-lfu.cpp
@@ -0,0 +1,74 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2013-2017 Regents of the University of California.
+ *
+ * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
+ *
+ * ndn-cxx library is free software: you can redistribute it and/or modify it under the
+ * terms of the GNU Lesser General Public License as published by the Free Software
+ * Foundation, either version 3 of the License, or (at your option) any later version.
+ *
+ * ndn-cxx library 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 Lesser General Public License for more details.
+ *
+ * You should have received copies of the GNU General Public License and GNU Lesser
+ * General Public License along with ndn-cxx, e.g., in COPYING.md file. If not, see
+ * <http://www.gnu.org/licenses/>.
+ *
+ * See AUTHORS.md for complete list of ndn-cxx authors and contributors.
+ */
+
+#include "in-memory-storage-lfu.hpp"
+
+namespace ndn {
+
+InMemoryStorageLfu::InMemoryStorageLfu(size_t limit)
+ : InMemoryStorage(limit)
+{
+}
+
+InMemoryStorageLfu::InMemoryStorageLfu(boost::asio::io_service& ioService, size_t limit)
+ : InMemoryStorage(ioService, limit)
+{
+}
+
+void
+InMemoryStorageLfu::afterInsert(InMemoryStorageEntry* entry)
+{
+ BOOST_ASSERT(m_cleanupIndex.size() <= size());
+ CleanupEntry cleanupEntry;
+ cleanupEntry.entry = entry;
+ cleanupEntry.frequency = 0;
+ m_cleanupIndex.insert(cleanupEntry);
+}
+
+bool
+InMemoryStorageLfu::evictItem()
+{
+ if (!m_cleanupIndex.get<byFrequency>().empty()) {
+ CleanupIndex::index<byFrequency>::type::iterator it = m_cleanupIndex.get<byFrequency>().begin();
+ eraseImpl(((*it).entry)->getFullName());
+ m_cleanupIndex.get<byFrequency>().erase(it);
+ return true;
+ }
+
+ return false;
+}
+
+void
+InMemoryStorageLfu::beforeErase(InMemoryStorageEntry* entry)
+{
+ CleanupIndex::index<byEntity>::type::iterator it = m_cleanupIndex.get<byEntity>().find(entry);
+ if (it != m_cleanupIndex.get<byEntity>().end())
+ m_cleanupIndex.get<byEntity>().erase(it);
+}
+
+void
+InMemoryStorageLfu::afterAccess(InMemoryStorageEntry* entry)
+{
+ CleanupIndex::index<byEntity>::type::iterator it = m_cleanupIndex.get<byEntity>().find(entry);
+ m_cleanupIndex.get<byEntity>().modify(it, &incrementFrequency);
+}
+
+} // namespace ndn
diff --git a/src/ims/in-memory-storage-lfu.hpp b/src/ims/in-memory-storage-lfu.hpp
new file mode 100644
index 0000000..7633cfd
--- /dev/null
+++ b/src/ims/in-memory-storage-lfu.hpp
@@ -0,0 +1,119 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2013-2017 Regents of the University of California.
+ *
+ * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
+ *
+ * ndn-cxx library is free software: you can redistribute it and/or modify it under the
+ * terms of the GNU Lesser General Public License as published by the Free Software
+ * Foundation, either version 3 of the License, or (at your option) any later version.
+ *
+ * ndn-cxx library 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 Lesser General Public License for more details.
+ *
+ * You should have received copies of the GNU General Public License and GNU Lesser
+ * General Public License along with ndn-cxx, e.g., in COPYING.md file. If not, see
+ * <http://www.gnu.org/licenses/>.
+ *
+ * See AUTHORS.md for complete list of ndn-cxx authors and contributors.
+ */
+
+#ifndef NDN_IMS_IN_MEMORY_STORAGE_LFU_HPP
+#define NDN_IMS_IN_MEMORY_STORAGE_LFU_HPP
+
+#include "in-memory-storage.hpp"
+
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/hashed_index.hpp>
+#include <boost/multi_index/identity.hpp>
+#include <boost/multi_index/member.hpp>
+#include <boost/multi_index/ordered_index.hpp>
+
+namespace ndn {
+
+/** @brief Provides an in-memory storage with Least Frequently Used (LFU) replacement policy.
+ * @note The frequency right now is usage count.
+ * @sa https://en.wikipedia.org/w/index.php?title=Least_frequently_used&oldid=604542656
+ */
+class InMemoryStorageLfu : public InMemoryStorage
+{
+public:
+ explicit
+ InMemoryStorageLfu(size_t limit = 10);
+
+ explicit
+ InMemoryStorageLfu(boost::asio::io_service& ioService, size_t limit = 10);
+
+NDN_CXX_PUBLIC_WITH_TESTS_ELSE_PROTECTED:
+ /** @brief Removes one Data packet from in-memory storage based on LFU, i.e. evict the least
+ * frequently accessed Data packet
+ * @return{ whether the Data was removed }
+ */
+ bool
+ evictItem() override;
+
+ /** @brief Update the entry when the entry is returned by the find() function,
+ * increment the frequency according to LFU
+ */
+ void
+ afterAccess(InMemoryStorageEntry* entry) override;
+
+ /** @brief Update the entry after a entry is successfully inserted, add it to the cleanupIndex
+ */
+ void
+ afterInsert(InMemoryStorageEntry* entry) override;
+
+ /** @brief Update the entry or other data structures before a entry is successfully erased,
+ * erase it from the cleanupIndex
+ */
+ void
+ beforeErase(InMemoryStorageEntry* entry) override;
+
+private:
+ // binds frequency and entry together
+ struct CleanupEntry
+ {
+ InMemoryStorageEntry* entry;
+ uint64_t frequency; // could potentially be overflowed
+ };
+
+ /** @brief Function to increment frequency of the entry in the CleanupEntry
+ */
+ static inline void
+ incrementFrequency(CleanupEntry& cleanupEntry)
+ {
+ ++cleanupEntry.frequency;
+ }
+
+private:
+ // multi_index_container to implement LFU
+ class byFrequency;
+ class byEntity;
+
+ typedef boost::multi_index_container<
+ CleanupEntry,
+ boost::multi_index::indexed_by<
+
+ // by Entry itself
+ boost::multi_index::hashed_unique<
+ boost::multi_index::tag<byEntity>,
+ boost::multi_index::member<CleanupEntry, InMemoryStorageEntry*, &CleanupEntry::entry>
+ >,
+
+ // by frequency (LFU)
+ boost::multi_index::ordered_non_unique<
+ boost::multi_index::tag<byFrequency>,
+ boost::multi_index::member<CleanupEntry, uint64_t, &CleanupEntry::frequency>,
+ std::less<uint64_t>
+ >
+
+ >
+ > CleanupIndex;
+
+ CleanupIndex m_cleanupIndex;
+};
+
+} // namespace ndn
+
+#endif // NDN_IMS_IN_MEMORY_STORAGE_LFU_HPP
diff --git a/src/ims/in-memory-storage-lru.cpp b/src/ims/in-memory-storage-lru.cpp
new file mode 100644
index 0000000..22c463d
--- /dev/null
+++ b/src/ims/in-memory-storage-lru.cpp
@@ -0,0 +1,73 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2013-2017 Regents of the University of California.
+ *
+ * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
+ *
+ * ndn-cxx library is free software: you can redistribute it and/or modify it under the
+ * terms of the GNU Lesser General Public License as published by the Free Software
+ * Foundation, either version 3 of the License, or (at your option) any later version.
+ *
+ * ndn-cxx library 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 Lesser General Public License for more details.
+ *
+ * You should have received copies of the GNU General Public License and GNU Lesser
+ * General Public License along with ndn-cxx, e.g., in COPYING.md file. If not, see
+ * <http://www.gnu.org/licenses/>.
+ *
+ * See AUTHORS.md for complete list of ndn-cxx authors and contributors.
+ */
+
+#include "in-memory-storage-lru.hpp"
+
+namespace ndn {
+
+InMemoryStorageLru::InMemoryStorageLru(size_t limit)
+ : InMemoryStorage(limit)
+{
+}
+
+InMemoryStorageLru::InMemoryStorageLru(boost::asio::io_service& ioService,
+ size_t limit)
+ : InMemoryStorage(ioService, limit)
+{
+}
+
+void
+InMemoryStorageLru::afterInsert(InMemoryStorageEntry* entry)
+{
+ BOOST_ASSERT(m_cleanupIndex.size() <= size());
+ InMemoryStorageEntry* ptr = entry;
+ m_cleanupIndex.insert(ptr);
+}
+
+bool
+InMemoryStorageLru::evictItem()
+{
+ if (!m_cleanupIndex.get<byUsedTime>().empty()) {
+ CleanupIndex::index<byUsedTime>::type::iterator it = m_cleanupIndex.get<byUsedTime>().begin();
+ eraseImpl((*it)->getFullName());
+ m_cleanupIndex.get<byUsedTime>().erase(it);
+ return true;
+ }
+
+ return false;
+}
+
+void
+InMemoryStorageLru::beforeErase(InMemoryStorageEntry* entry)
+{
+ CleanupIndex::index<byEntity>::type::iterator it = m_cleanupIndex.get<byEntity>().find(entry);
+ if (it != m_cleanupIndex.get<byEntity>().end())
+ m_cleanupIndex.get<byEntity>().erase(it);
+}
+
+void
+InMemoryStorageLru::afterAccess(InMemoryStorageEntry* entry)
+{
+ beforeErase(entry);
+ afterInsert(entry);
+}
+
+} // namespace ndn
diff --git a/src/ims/in-memory-storage-lru.hpp b/src/ims/in-memory-storage-lru.hpp
new file mode 100644
index 0000000..3dd9dfe
--- /dev/null
+++ b/src/ims/in-memory-storage-lru.hpp
@@ -0,0 +1,98 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2013-2017 Regents of the University of California.
+ *
+ * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
+ *
+ * ndn-cxx library is free software: you can redistribute it and/or modify it under the
+ * terms of the GNU Lesser General Public License as published by the Free Software
+ * Foundation, either version 3 of the License, or (at your option) any later version.
+ *
+ * ndn-cxx library 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 Lesser General Public License for more details.
+ *
+ * You should have received copies of the GNU General Public License and GNU Lesser
+ * General Public License along with ndn-cxx, e.g., in COPYING.md file. If not, see
+ * <http://www.gnu.org/licenses/>.
+ *
+ * See AUTHORS.md for complete list of ndn-cxx authors and contributors.
+ */
+
+#ifndef NDN_IMS_IN_MEMORY_STORAGE_LRU_HPP
+#define NDN_IMS_IN_MEMORY_STORAGE_LRU_HPP
+
+#include "in-memory-storage.hpp"
+
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/hashed_index.hpp>
+#include <boost/multi_index/identity.hpp>
+#include <boost/multi_index/member.hpp>
+#include <boost/multi_index/sequenced_index.hpp>
+
+namespace ndn {
+
+/** @brief Provides in-memory storage employing Least Recently Used (LRU) replacement policy.
+ */
+class InMemoryStorageLru : public InMemoryStorage
+{
+public:
+ explicit
+ InMemoryStorageLru(size_t limit = 10);
+
+ InMemoryStorageLru(boost::asio::io_service& ioService, size_t limit = 10);
+
+NDN_CXX_PUBLIC_WITH_TESTS_ELSE_PROTECTED:
+ /** @brief Removes one Data packet from in-memory storage based on LRU, i.e. evict the least
+ * recently accessed Data packet
+ * @return{ whether the Data was removed }
+ */
+ bool
+ evictItem() override;
+
+ /** @brief Update the entry when the entry is returned by the find() function,
+ * update the last used time according to LRU
+ */
+ void
+ afterAccess(InMemoryStorageEntry* entry) override;
+
+ /** @brief Update the entry after a entry is successfully inserted, add it to the cleanupIndex
+ */
+ void
+ afterInsert(InMemoryStorageEntry* entry) override;
+
+ /** @brief Update the entry or other data structures before a entry is successfully erased,
+ * erase it from the cleanupIndex
+ */
+ void
+ beforeErase(InMemoryStorageEntry* entry) override;
+
+private:
+ // multi_index_container to implement LRU
+ class byUsedTime;
+ class byEntity;
+
+ typedef boost::multi_index_container<
+ InMemoryStorageEntry*,
+ boost::multi_index::indexed_by<
+
+ // by Entry itself
+ boost::multi_index::hashed_unique<
+ boost::multi_index::tag<byEntity>,
+ boost::multi_index::identity<InMemoryStorageEntry*>
+ >,
+
+ // by last used time (LRU)
+ boost::multi_index::sequenced<
+ boost::multi_index::tag<byUsedTime>
+ >
+
+ >
+ > CleanupIndex;
+
+ CleanupIndex m_cleanupIndex;
+};
+
+} // namespace ndn
+
+#endif // NDN_IMS_IN_MEMORY_STORAGE_LRU_HPP
diff --git a/src/ims/in-memory-storage-persistent.cpp b/src/ims/in-memory-storage-persistent.cpp
new file mode 100644
index 0000000..ff6a3a9
--- /dev/null
+++ b/src/ims/in-memory-storage-persistent.cpp
@@ -0,0 +1,42 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2013-2017 Regents of the University of California.
+ *
+ * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
+ *
+ * ndn-cxx library is free software: you can redistribute it and/or modify it under the
+ * terms of the GNU Lesser General Public License as published by the Free Software
+ * Foundation, either version 3 of the License, or (at your option) any later version.
+ *
+ * ndn-cxx library 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 Lesser General Public License for more details.
+ *
+ * You should have received copies of the GNU General Public License and GNU Lesser
+ * General Public License along with ndn-cxx, e.g., in COPYING.md file. If not, see
+ * <http://www.gnu.org/licenses/>.
+ *
+ * See AUTHORS.md for complete list of ndn-cxx authors and contributors.
+ */
+
+#include "in-memory-storage-persistent.hpp"
+
+namespace ndn {
+
+InMemoryStoragePersistent::InMemoryStoragePersistent()
+ : InMemoryStorage()
+{
+}
+
+InMemoryStoragePersistent::InMemoryStoragePersistent(boost::asio::io_service& ioService)
+ : InMemoryStorage(ioService)
+{
+}
+
+bool
+InMemoryStoragePersistent::evictItem()
+{
+ return false;
+}
+
+} // namespace ndn
diff --git a/src/ims/in-memory-storage-persistent.hpp b/src/ims/in-memory-storage-persistent.hpp
new file mode 100644
index 0000000..5920ef3
--- /dev/null
+++ b/src/ims/in-memory-storage-persistent.hpp
@@ -0,0 +1,53 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2013-2017 Regents of the University of California.
+ *
+ * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
+ *
+ * ndn-cxx library is free software: you can redistribute it and/or modify it under the
+ * terms of the GNU Lesser General Public License as published by the Free Software
+ * Foundation, either version 3 of the License, or (at your option) any later version.
+ *
+ * ndn-cxx library 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 Lesser General Public License for more details.
+ *
+ * You should have received copies of the GNU General Public License and GNU Lesser
+ * General Public License along with ndn-cxx, e.g., in COPYING.md file. If not, see
+ * <http://www.gnu.org/licenses/>.
+ *
+ * See AUTHORS.md for complete list of ndn-cxx authors and contributors.
+ */
+
+#ifndef NDN_IMS_IN_MEMORY_STORAGE_PERSISTENT_HPP
+#define NDN_IMS_IN_MEMORY_STORAGE_PERSISTENT_HPP
+
+#include "in-memory-storage.hpp"
+
+namespace ndn {
+
+/** @brief Provides application cache with persistent storage, of which no replacement policy will
+ * be employed. Entries will only be deleted by explicit application control.
+ */
+class InMemoryStoragePersistent : public InMemoryStorage
+{
+public:
+ InMemoryStoragePersistent();
+
+ explicit
+ InMemoryStoragePersistent(boost::asio::io_service& ioService);
+
+NDN_CXX_PUBLIC_WITH_TESTS_ELSE_PROTECTED:
+ /** @brief Do nothing.
+ *
+ * This storage is persistent, and does not support eviction.
+ *
+ * @return false
+ */
+ bool
+ evictItem() override;
+};
+
+} // namespace ndn
+
+#endif // NDN_IMS_IN_MEMORY_STORAGE_PERSISTENT_HPP
diff --git a/src/ims/in-memory-storage.cpp b/src/ims/in-memory-storage.cpp
new file mode 100644
index 0000000..0dc7df7
--- /dev/null
+++ b/src/ims/in-memory-storage.cpp
@@ -0,0 +1,449 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2013-2017 Regents of the University of California.
+ *
+ * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
+ *
+ * ndn-cxx library is free software: you can redistribute it and/or modify it under the
+ * terms of the GNU Lesser General Public License as published by the Free Software
+ * Foundation, either version 3 of the License, or (at your option) any later version.
+ *
+ * ndn-cxx library 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 Lesser General Public License for more details.
+ *
+ * You should have received copies of the GNU General Public License and GNU Lesser
+ * General Public License along with ndn-cxx, e.g., in COPYING.md file. If not, see
+ * <http://www.gnu.org/licenses/>.
+ *
+ * See AUTHORS.md for complete list of ndn-cxx authors and contributors.
+ */
+
+#include "in-memory-storage.hpp"
+#include "in-memory-storage-entry.hpp"
+
+namespace ndn {
+
+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)
+ , m_cache(cache)
+ , m_it(it)
+{
+}
+
+InMemoryStorage::const_iterator&
+InMemoryStorage::const_iterator::operator++()
+{
+ m_it++;
+ if (m_it != m_cache->get<byFullName>().end()) {
+ m_ptr = &((*m_it)->getData());
+ }
+ else {
+ m_ptr = 0;
+ }
+
+ return *this;
+}
+
+InMemoryStorage::const_iterator
+InMemoryStorage::const_iterator::operator++(int)
+{
+ InMemoryStorage::const_iterator i(*this);
+ this->operator++();
+ return i;
+}
+
+const Data&
+InMemoryStorage::const_iterator::operator*()
+{
+ return *m_ptr;
+}
+
+const Data*
+InMemoryStorage::const_iterator::operator->()
+{
+ return m_ptr;
+}
+
+bool
+InMemoryStorage::const_iterator::operator==(const const_iterator& rhs)
+{
+ return m_it == rhs.m_it;
+}
+
+bool
+InMemoryStorage::const_iterator::operator!=(const const_iterator& rhs)
+{
+ return m_it != rhs.m_it;
+}
+
+InMemoryStorage::InMemoryStorage(size_t limit)
+ : 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 (m_limit != std::numeric_limits<size_t>::max() && m_capacity > m_limit) {
+ m_capacity = m_limit;
+ }
+
+ for (size_t i = 0; i < m_capacity; i++) {
+ m_freeEntries.push(new InMemoryStorageEntry());
+ }
+}
+
+InMemoryStorage::~InMemoryStorage()
+{
+ // evict all items from cache
+ Cache::iterator it = m_cache.begin();
+ while (it != m_cache.end()) {
+ it = freeEntry(it);
+ }
+
+ BOOST_ASSERT(m_freeEntries.size() == m_capacity);
+
+ while (!m_freeEntries.empty()) {
+ delete m_freeEntries.top();
+ m_freeEntries.pop();
+ }
+}
+
+void
+InMemoryStorage::setCapacity(size_t capacity)
+{
+ size_t oldCapacity = m_capacity;
+ m_capacity = capacity;
+
+ if (size() > m_capacity) {
+ ssize_t nAllowedFailures = size() - m_capacity;
+ while (size() > m_capacity) {
+ if (!evictItem() && --nAllowedFailures < 0) {
+ BOOST_THROW_EXCEPTION(Error());
+ }
+ }
+ }
+
+ if (m_capacity >= oldCapacity) {
+ for (size_t i = oldCapacity; i < m_capacity; i++) {
+ m_freeEntries.push(new InMemoryStorageEntry());
+ }
+ }
+ else {
+ for (size_t i = oldCapacity; i > m_capacity; i--) {
+ delete m_freeEntries.top();
+ m_freeEntries.pop();
+ }
+ }
+
+ BOOST_ASSERT(size() + m_freeEntries.size() == m_capacity);
+}
+
+void
+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());
+ if (it != m_cache.get<byFullName>().end())
+ return;
+
+ //if full, double the capacity
+ bool doesReachLimit = (getLimit() == getCapacity());
+ if (isFull() && !doesReachLimit) {
+ // note: This is incorrect if 2*capacity overflows, but memory should run out before that
+ size_t newCapacity = std::min(2 * getCapacity(), getLimit());
+ setCapacity(newCapacity);
+ }
+
+ //if full and reach limitation of the capacity, employ replacement policy
+ if (isFull() && doesReachLimit) {
+ evictItem();
+ }
+
+ //insert to cache
+ BOOST_ASSERT(m_freeEntries.size() > 0);
+ // take entry for the memory pool
+ InMemoryStorageEntry* entry = m_freeEntries.top();
+ m_freeEntries.pop();
+ m_nPackets++;
+ entry->setData(data);
+ if (m_scheduler != nullptr && mustBeFreshProcessingWindow > ZERO_WINDOW) {
+ auto eventId = make_unique<util::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
+ afterInsert(entry);
+}
+
+shared_ptr<const Data>
+InMemoryStorage::find(const Name& name)
+{
+ Cache::index<byFullName>::type::iterator it = m_cache.get<byFullName>().lower_bound(name);
+
+ //if not found, return null
+ if (it == m_cache.get<byFullName>().end()) {
+ return shared_ptr<const Data>();
+ }
+
+ //if the given name is not the prefix of the lower_bound, return null
+ if (!name.isPrefixOf((*it)->getFullName())) {
+ return shared_ptr<const Data>();
+ }
+
+ afterAccess(*it);
+ return ((*it)->getData()).shared_from_this();
+}
+
+shared_ptr<const Data>
+InMemoryStorage::find(const Interest& interest)
+{
+ //if the interest contains implicit digest, it is possible to directly locate a packet.
+ Cache::index<byFullName>::type::iterator it = m_cache.get<byFullName>()
+ .find(interest.getName());
+
+ //if a packet is located by its full name, it must be the packet to return.
+ if (it != m_cache.get<byFullName>().end()) {
+ return ((*it)->getData()).shared_from_this();
+ }
+
+ //if the packet is not discovered by last step, either the packet is not in the storage or
+ //the interest doesn't contains implicit digest.
+ it = m_cache.get<byFullName>().lower_bound(interest.getName());
+
+ if (it == m_cache.get<byFullName>().end()) {
+ 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--;
+
+ InMemoryStorageEntry* ret = selectChild(interest, it);
+ if (ret != 0) {
+ //let derived class do something with the entry
+ afterAccess(ret);
+ return ret->getData().shared_from_this();
+ }
+ else {
+ return shared_ptr<const Data>();
+ }
+}
+
+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
+{
+ BOOST_ASSERT(startingPoint != m_cache.get<byFullName>().end());
+
+ if (startingPoint != m_cache.get<byFullName>().begin())
+ {
+ BOOST_ASSERT((*startingPoint)->getFullName() < interest.getName());
+ }
+
+ 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()))
+ {
+ return *startingPoint;
+ }
+ }
+
+ //iterate to the right
+ Cache::index<byFullName>::type::iterator rightmost = startingPoint;
+ if (startingPoint != m_cache.get<byFullName>().end())
+ {
+ Cache::index<byFullName>::type::iterator rightmostCandidate = startingPoint;
+ Name currentChildPrefix("");
+
+ while (true)
+ {
+ ++rightmostCandidate;
+ // filter out "stale" data
+ if (interest.getMustBeFresh())
+ rightmostCandidate = findNextFresh(rightmostCandidate);
+
+ bool isInBoundaries = (rightmostCandidate != m_cache.get<byFullName>().end());
+ bool isInPrefix = false;
+ if (isInBoundaries)
+ {
+ isInPrefix = interest.getName().isPrefixOf((*rightmostCandidate)->getFullName());
+ }
+
+ if (isInPrefix)
+ {
+ if (interest.matchesData((*rightmostCandidate)->getData()))
+ {
+ if (hasLeftmostSelector)
+ {
+ return *rightmostCandidate;
+ }
+
+ if (hasRightmostSelector)
+ {
+ // get prefix which is one component longer than Interest name
+ const Name& childPrefix = (*rightmostCandidate)->getFullName()
+ .getPrefix(interest.getName().size() + 1);
+
+ if (currentChildPrefix.empty() || (childPrefix != currentChildPrefix))
+ {
+ currentChildPrefix = childPrefix;
+ rightmost = rightmostCandidate;
+ }
+ }
+ }
+ }
+ else
+ break;
+ }
+ }
+
+ if (rightmost != startingPoint)
+ {
+ return *rightmost;
+ }
+
+ if (hasRightmostSelector) // if rightmost was not found, try starting point
+ {
+ if (interest.matchesData((*startingPoint)->getData()))
+ {
+ return *startingPoint;
+ }
+ }
+
+ return 0;
+}
+
+InMemoryStorage::Cache::iterator
+InMemoryStorage::freeEntry(Cache::iterator it)
+{
+ //push the *empty* entry into mem pool
+ (*it)->release();
+ m_freeEntries.push(*it);
+ m_nPackets--;
+ return m_cache.erase(it);
+}
+
+void
+InMemoryStorage::erase(const Name& prefix, const bool isPrefix)
+{
+ if (isPrefix) {
+ Cache::index<byFullName>::type::iterator it = m_cache.get<byFullName>().lower_bound(prefix);
+
+ while (it != m_cache.get<byFullName>().end() && prefix.isPrefixOf((*it)->getName())) {
+ //let derived class do something with the entry
+ beforeErase(*it);
+ it = freeEntry(it);
+ }
+ }
+ else {
+ Cache::index<byFullName>::type::iterator it = m_cache.get<byFullName>().find(prefix);
+
+ if (it == m_cache.get<byFullName>().end())
+ return;
+
+ //let derived class do something with the entry
+ beforeErase(*it);
+ freeEntry(it);
+ }
+
+ if (m_freeEntries.size() > (2 * size()))
+ setCapacity(getCapacity() / 2);
+}
+
+void
+InMemoryStorage::eraseImpl(const Name& name)
+{
+ Cache::index<byFullName>::type::iterator it = m_cache.get<byFullName>().find(name);
+
+ if (it == m_cache.get<byFullName>().end())
+ return;
+
+ freeEntry(it);
+}
+
+InMemoryStorage::const_iterator
+InMemoryStorage::begin() const
+{
+ Cache::index<byFullName>::type::iterator it = m_cache.get<byFullName>().begin();
+
+ return const_iterator(&((*it)->getData()), &m_cache, it);
+}
+
+InMemoryStorage::const_iterator
+InMemoryStorage::end() const
+{
+ Cache::index<byFullName>::type::iterator it = m_cache.get<byFullName>().end();
+
+ return const_iterator(nullptr, &m_cache, it);
+}
+
+void
+InMemoryStorage::afterInsert(InMemoryStorageEntry* entry)
+{
+}
+
+void
+InMemoryStorage::beforeErase(InMemoryStorageEntry* entry)
+{
+}
+
+void
+InMemoryStorage::afterAccess(InMemoryStorageEntry* entry)
+{
+}
+
+void
+InMemoryStorage::printCache(std::ostream& os) const
+{
+ //start from the upper layer towards bottom
+ const Cache::index<byFullName>::type& cacheIndex = m_cache.get<byFullName>();
+ for (Cache::index<byFullName>::type::iterator it = cacheIndex.begin();
+ it != cacheIndex.end(); it++)
+ os << (*it)->getFullName() << std::endl;
+}
+
+} // namespace ndn
diff --git a/src/ims/in-memory-storage.hpp b/src/ims/in-memory-storage.hpp
new file mode 100644
index 0000000..9e61e7a
--- /dev/null
+++ b/src/ims/in-memory-storage.hpp
@@ -0,0 +1,341 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2013-2017 Regents of the University of California.
+ *
+ * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
+ *
+ * ndn-cxx library is free software: you can redistribute it and/or modify it under the
+ * terms of the GNU Lesser General Public License as published by the Free Software
+ * Foundation, either version 3 of the License, or (at your option) any later version.
+ *
+ * ndn-cxx library 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 Lesser General Public License for more details.
+ *
+ * You should have received copies of the GNU General Public License and GNU Lesser
+ * General Public License along with ndn-cxx, e.g., in COPYING.md file. If not, see
+ * <http://www.gnu.org/licenses/>.
+ *
+ * See AUTHORS.md for complete list of ndn-cxx authors and contributors.
+ */
+
+#ifndef NDN_IMS_IN_MEMORY_STORAGE_HPP
+#define NDN_IMS_IN_MEMORY_STORAGE_HPP
+
+#include "in-memory-storage-entry.hpp"
+
+#include <iterator>
+#include <stack>
+
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/identity.hpp>
+#include <boost/multi_index/mem_fun.hpp>
+#include <boost/multi_index/member.hpp>
+#include <boost/multi_index/ordered_index.hpp>
+#include <boost/multi_index/sequenced_index.hpp>
+
+namespace ndn {
+
+/** @brief Represents in-memory storage
+ */
+class InMemoryStorage : noncopyable
+{
+public:
+ // multi_index_container to implement storage
+ class byFullName;
+
+ typedef boost::multi_index_container<
+ InMemoryStorageEntry*,
+ boost::multi_index::indexed_by<
+
+ // by Full Name
+ boost::multi_index::ordered_unique<
+ boost::multi_index::tag<byFullName>,
+ boost::multi_index::const_mem_fun<InMemoryStorageEntry, const Name&,
+ &InMemoryStorageEntry::getFullName>,
+ std::less<Name>
+ >
+
+ >
+ > Cache;
+
+ /** @brief Represents a self-defined const_iterator for the in-memory storage
+ *
+ * @note Don't try to instantiate this class directly, use InMemoryStorage::begin() instead.
+ */
+ class const_iterator : public std::iterator<std::input_iterator_tag, const Data>
+ {
+ public:
+ const_iterator(const Data* ptr, const Cache* cache,
+ Cache::index<byFullName>::type::iterator it);
+
+ const_iterator&
+ operator++();
+
+ const_iterator
+ operator++(int);
+
+ const Data&
+ operator*();
+
+ const Data*
+ operator->();
+
+ bool
+ operator==(const const_iterator& rhs);
+
+ bool
+ operator!=(const const_iterator& rhs);
+
+ private:
+ const Data* m_ptr;
+ const Cache* m_cache;
+ Cache::index<byFullName>::type::iterator m_it;
+ };
+
+ /** @brief Represents an error might be thrown during reduce the current capacity of the
+ * in-memory storage through function setCapacity(size_t nMaxPackets).
+ */
+ class Error : public std::runtime_error
+ {
+ public:
+ Error()
+ : std::runtime_error("Cannot reduce the capacity of the in-memory storage!")
+ {
+ }
+ };
+
+ /** @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
+ */
+ virtual
+ ~InMemoryStorage();
+
+ /** @brief Inserts a Data packet
+ *
+ * @param data the packet to insert, must be signed and have wire encoding
+ * @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.
+ *
+ * @note It will invoke afterInsert(shared_ptr<InMemoryStorageEntry>).
+ */
+ void
+ insert(const Data& data, const time::milliseconds& mustBeFreshProcessingWindow = INFINITE_WINDOW);
+
+ /** @brief Finds the best match Data for an Interest
+ *
+ * @note It will invoke afterAccess(shared_ptr<InMemoryStorageEntry>).
+ * As currently it is impossible to determine whether a Name contains implicit digest or not,
+ * therefore this find function is not able to locate a packet according to an interest(
+ * including implicit digest) whose name is not the full name of the data matching the
+ * implicit digest.
+ *
+ * @return{ the best match, if any; otherwise a null shared_ptr }
+ */
+ shared_ptr<const Data>
+ find(const Interest& interest);
+
+ /** @brief Finds the best match Data for a Name with or without
+ * the implicit digest.
+ *
+ * If packets with the same name but different digests exist
+ * and the Name supplied is the one without implicit digest, a packet
+ * will be arbitrarily chosen to return.
+ *
+ * @note It will invoke afterAccess(shared_ptr<InMemoryStorageEntry>).
+ *
+ * @return{ the one matched the Name; otherwise a null shared_ptr }
+ */
+ shared_ptr<const Data>
+ find(const Name& name);
+
+ /** @brief Deletes in-memory storage entry by prefix by default.
+ * @param prefix Exact name of a prefix of the data to remove
+ * @param isPrefix If false, the function will only delete the
+ * entry completely matched with the prefix according to canonical ordering.
+ * For this case, user should substitute the prefix with full name.
+ *
+ * @note Please do not use this function directly in any derived class to erase
+ * entry in the cache, use eraseHelper instead.
+ * @note It will invoke beforeErase(shared_ptr<InMemoryStorageEntry>).
+ */
+ void
+ erase(const Name& prefix, const bool isPrefix = true);
+
+ /** @return{ maximum number of packets that can be allowed to store in in-memory storage }
+ */
+ size_t
+ getLimit() const
+ {
+ return m_limit;
+ }
+
+ /** @return{ number of packets stored in in-memory storage }
+ */
+ size_t
+ size() const
+ {
+ return m_nPackets;
+ }
+
+ /** @brief Returns begin iterator of the in-memory storage ordering by
+ * name with digest
+ *
+ * @return{ const_iterator pointing to the beginning of the m_cache }
+ */
+ InMemoryStorage::const_iterator
+ begin() const;
+
+ /** @brief Returns end iterator of the in-memory storage ordering by
+ * name with digest
+ *
+ * @return{ const_iterator pointing to the end of the m_cache }
+ */
+ InMemoryStorage::const_iterator
+ end() const;
+
+NDN_CXX_PUBLIC_WITH_TESTS_ELSE_PROTECTED:
+ /** @brief Update the entry when the entry is returned by the find() function
+ * according to derived class implemented replacement policy
+ */
+ virtual void
+ afterAccess(InMemoryStorageEntry* entry);
+
+ /** @brief Update the entry or other data structures
+ * after a entry is successfully inserted
+ * according to derived class implemented replacement policy
+ */
+ virtual void
+ afterInsert(InMemoryStorageEntry* entry);
+
+ /** @brief Update the entry or other data structures
+ * before a entry is successfully erased
+ * according to derived class implemented replacement policy
+ */
+ virtual void
+ beforeErase(InMemoryStorageEntry* entry);
+
+ /** @brief Removes one Data packet from in-memory storage based on
+ * derived class implemented replacement policy
+ *
+ * Please do not use this function directly in any derived class to erase
+ * entry in the cache, use eraseHelper instead.
+ * @return{ whether the Data was removed }
+ */
+ virtual bool
+ evictItem() = 0;
+
+NDN_CXX_PUBLIC_WITH_TESTS_ELSE_PROTECTED:
+ /** @brief sets current capacity of in-memory storage (in packets)
+ */
+ void
+ setCapacity(size_t nMaxPackets);
+
+ /** @brief returns current capacity of in-memory storage (in packets)
+ * @return{ number of packets that can be stored in application cache }
+ */
+ size_t
+ getCapacity() const
+ {
+ return m_capacity;
+ }
+
+ /** @brief returns true if the in-memory storage uses up the current capacity, false otherwise
+ */
+ bool
+ isFull() const
+ {
+ return size() >= m_capacity;
+ }
+
+ /** @brief deletes in-memory storage entries by the Name with implicit digest.
+ *
+ * This is the function one should use to erase entry in the cache
+ * in derived class.
+ * It won't invoke beforeErase(shared_ptr<Entry>).
+ */
+ void
+ eraseImpl(const Name& name);
+
+ /** @brief Prints contents of the in-memory storage
+ */
+ void
+ printCache(std::ostream& os) const;
+
+NDN_CXX_PUBLIC_WITH_TESTS_ELSE_PRIVATE:
+ /** @brief free in-memory storage entries by an iterator pointing to that entry.
+ @return An iterator pointing to the element that followed the last element erased.
+ */
+ Cache::iterator
+ freeEntry(Cache::iterator it);
+
+ /** @brief Implements child selector (leftmost, rightmost, undeclared).
+ * Operates on the first layer of a skip list.
+ *
+ * startingPoint must be less than Interest Name.
+ * startingPoint can be equal to Interest Name only
+ * when the item is in the begin() position.
+ *
+ * Iterates toward greater Names, terminates when application cache entry falls out of Interest
+ * prefix. When childSelector = leftmost, returns first application cache entry that satisfies
+ * other selectors. When childSelector = rightmost, it goes till the end, and returns application
+ * cache entry that satisfies other selectors. Returned application cache entry is the leftmost
+ * child of the rightmost child.
+ * @return{ the best match, if any; otherwise 0 }
+ */
+ InMemoryStorageEntry*
+ 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
+ size_t m_limit;
+ /// current capacity of the in-memory storage in packets
+ size_t m_capacity;
+ /// current number of packets in in-memory storage
+ size_t m_nPackets;
+ /// memory pool
+ std::stack<InMemoryStorageEntry*> m_freeEntries;
+ /// scheduler
+ unique_ptr<Scheduler> m_scheduler;
+};
+
+} // namespace ndn
+
+#endif // NDN_IMS_IN_MEMORY_STORAGE_HPP