blob: 7633cfd48d0909b8cba59f13f01614ab0665254b [file] [log] [blame]
Jiewen Tan99135962014-09-20 02:18:53 -07001/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
Junxiao Shic542f632017-07-18 14:20:32 +00002/*
3 * Copyright (c) 2013-2017 Regents of the University of California.
Jiewen Tan99135962014-09-20 02:18:53 -07004 *
5 * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
6 *
7 * ndn-cxx library is free software: you can redistribute it and/or modify it under the
8 * terms of the GNU Lesser General Public License as published by the Free Software
9 * Foundation, either version 3 of the License, or (at your option) any later version.
10 *
11 * ndn-cxx library is distributed in the hope that it will be useful, but WITHOUT ANY
12 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
13 * PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.
14 *
15 * You should have received copies of the GNU General Public License and GNU Lesser
16 * General Public License along with ndn-cxx, e.g., in COPYING.md file. If not, see
17 * <http://www.gnu.org/licenses/>.
18 *
19 * See AUTHORS.md for complete list of ndn-cxx authors and contributors.
20 */
21
Junxiao Shic542f632017-07-18 14:20:32 +000022#ifndef NDN_IMS_IN_MEMORY_STORAGE_LFU_HPP
23#define NDN_IMS_IN_MEMORY_STORAGE_LFU_HPP
Jiewen Tan99135962014-09-20 02:18:53 -070024
25#include "in-memory-storage.hpp"
26
Jiewen Tan99135962014-09-20 02:18:53 -070027#include <boost/multi_index_container.hpp>
Jiewen Tan99135962014-09-20 02:18:53 -070028#include <boost/multi_index/hashed_index.hpp>
29#include <boost/multi_index/identity.hpp>
Junxiao Shic542f632017-07-18 14:20:32 +000030#include <boost/multi_index/member.hpp>
31#include <boost/multi_index/ordered_index.hpp>
Jiewen Tan99135962014-09-20 02:18:53 -070032
33namespace ndn {
Jiewen Tan99135962014-09-20 02:18:53 -070034
35/** @brief Provides an in-memory storage with Least Frequently Used (LFU) replacement policy.
36 * @note The frequency right now is usage count.
37 * @sa https://en.wikipedia.org/w/index.php?title=Least_frequently_used&oldid=604542656
38 */
39class InMemoryStorageLfu : public InMemoryStorage
40{
41public:
42 explicit
43 InMemoryStorageLfu(size_t limit = 10);
44
Yingdi Yu404eafd2016-03-06 14:54:25 -080045 explicit
46 InMemoryStorageLfu(boost::asio::io_service& ioService, size_t limit = 10);
47
Junxiao Shi99848502014-10-13 19:22:22 -070048NDN_CXX_PUBLIC_WITH_TESTS_ELSE_PROTECTED:
Jiewen Tan99135962014-09-20 02:18:53 -070049 /** @brief Removes one Data packet from in-memory storage based on LFU, i.e. evict the least
50 * frequently accessed Data packet
51 * @return{ whether the Data was removed }
52 */
Davide Pesavento57c07df2016-12-11 18:41:45 -050053 bool
Davide Pesaventoaeeb3fc2016-08-14 03:40:02 +020054 evictItem() override;
Jiewen Tan99135962014-09-20 02:18:53 -070055
56 /** @brief Update the entry when the entry is returned by the find() function,
57 * increment the frequency according to LFU
58 */
Davide Pesavento57c07df2016-12-11 18:41:45 -050059 void
Davide Pesaventoaeeb3fc2016-08-14 03:40:02 +020060 afterAccess(InMemoryStorageEntry* entry) override;
Jiewen Tan99135962014-09-20 02:18:53 -070061
62 /** @brief Update the entry after a entry is successfully inserted, add it to the cleanupIndex
63 */
Davide Pesavento57c07df2016-12-11 18:41:45 -050064 void
Davide Pesaventoaeeb3fc2016-08-14 03:40:02 +020065 afterInsert(InMemoryStorageEntry* entry) override;
Jiewen Tan99135962014-09-20 02:18:53 -070066
67 /** @brief Update the entry or other data structures before a entry is successfully erased,
68 * erase it from the cleanupIndex
69 */
Davide Pesavento57c07df2016-12-11 18:41:45 -050070 void
Davide Pesaventoaeeb3fc2016-08-14 03:40:02 +020071 beforeErase(InMemoryStorageEntry* entry) override;
Jiewen Tan99135962014-09-20 02:18:53 -070072
73private:
Davide Pesaventoaeeb3fc2016-08-14 03:40:02 +020074 // binds frequency and entry together
Jiewen Tan99135962014-09-20 02:18:53 -070075 struct CleanupEntry
76 {
77 InMemoryStorageEntry* entry;
Davide Pesaventoaeeb3fc2016-08-14 03:40:02 +020078 uint64_t frequency; // could potentially be overflowed
Jiewen Tan99135962014-09-20 02:18:53 -070079 };
80
81 /** @brief Function to increment frequency of the entry in the CleanupEntry
82 */
83 static inline void
84 incrementFrequency(CleanupEntry& cleanupEntry)
85 {
86 ++cleanupEntry.frequency;
87 }
88
89private:
Junxiao Shic542f632017-07-18 14:20:32 +000090 // multi_index_container to implement LFU
Jiewen Tan99135962014-09-20 02:18:53 -070091 class byFrequency;
92 class byEntity;
93
94 typedef boost::multi_index_container<
95 CleanupEntry,
96 boost::multi_index::indexed_by<
97
98 // by Entry itself
99 boost::multi_index::hashed_unique<
100 boost::multi_index::tag<byEntity>,
101 boost::multi_index::member<CleanupEntry, InMemoryStorageEntry*, &CleanupEntry::entry>
102 >,
103
104 // by frequency (LFU)
105 boost::multi_index::ordered_non_unique<
106 boost::multi_index::tag<byFrequency>,
107 boost::multi_index::member<CleanupEntry, uint64_t, &CleanupEntry::frequency>,
108 std::less<uint64_t>
109 >
110
111 >
112 > CleanupIndex;
113
114 CleanupIndex m_cleanupIndex;
115};
116
Jiewen Tan99135962014-09-20 02:18:53 -0700117} // namespace ndn
118
Junxiao Shic542f632017-07-18 14:20:32 +0000119#endif // NDN_IMS_IN_MEMORY_STORAGE_LFU_HPP