blob: ac8a02de5eb22731673bd1319e9768fabc84230d [file] [log] [blame]
Jiewen Tan99135962014-09-20 02:18:53 -07001/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2/**
3 * Copyright (c) 2013-2014 Regents of the University of California.
4 *
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
22#ifndef NDN_UTIL_IN_MEMORY_STORAGE_LFU_HPP
23#define NDN_UTIL_IN_MEMORY_STORAGE_LFU_HPP
24
25#include "in-memory-storage.hpp"
26
27#include <boost/multi_index/member.hpp>
28#include <boost/multi_index_container.hpp>
29#include <boost/multi_index/ordered_index.hpp>
30#include <boost/multi_index/hashed_index.hpp>
31#include <boost/multi_index/identity.hpp>
32
33namespace ndn {
34namespace util {
35
36/** @brief Provides an in-memory storage with Least Frequently Used (LFU) replacement policy.
37 * @note The frequency right now is usage count.
38 * @sa https://en.wikipedia.org/w/index.php?title=Least_frequently_used&oldid=604542656
39 */
40class InMemoryStorageLfu : public InMemoryStorage
41{
42public:
43 explicit
44 InMemoryStorageLfu(size_t limit = 10);
45
46 virtual
47 ~InMemoryStorageLfu();
48
Junxiao Shi99848502014-10-13 19:22:22 -070049NDN_CXX_PUBLIC_WITH_TESTS_ELSE_PROTECTED:
Jiewen Tan99135962014-09-20 02:18:53 -070050 /** @brief Removes one Data packet from in-memory storage based on LFU, i.e. evict the least
51 * frequently accessed Data packet
52 * @return{ whether the Data was removed }
53 */
54 virtual bool
55 evictItem();
56
57 /** @brief Update the entry when the entry is returned by the find() function,
58 * increment the frequency according to LFU
59 */
60 virtual void
61 afterAccess(InMemoryStorageEntry* entry);
62
63 /** @brief Update the entry after a entry is successfully inserted, add it to the cleanupIndex
64 */
65 virtual void
66 afterInsert(InMemoryStorageEntry* entry);
67
68 /** @brief Update the entry or other data structures before a entry is successfully erased,
69 * erase it from the cleanupIndex
70 */
71 virtual void
72 beforeErase(InMemoryStorageEntry* entry);
73
74private:
75 //binds frequency and entry together
76 struct CleanupEntry
77 {
78 InMemoryStorageEntry* entry;
79 uint64_t frequency;//could potentially be overflowed
80 };
81
82 /** @brief Function to increment frequency of the entry in the CleanupEntry
83 */
84 static inline void
85 incrementFrequency(CleanupEntry& cleanupEntry)
86 {
87 ++cleanupEntry.frequency;
88 }
89
90private:
91 //multi_index_container to implement LFU
92 class byFrequency;
93 class byEntity;
94
95 typedef boost::multi_index_container<
96 CleanupEntry,
97 boost::multi_index::indexed_by<
98
99 // by Entry itself
100 boost::multi_index::hashed_unique<
101 boost::multi_index::tag<byEntity>,
102 boost::multi_index::member<CleanupEntry, InMemoryStorageEntry*, &CleanupEntry::entry>
103 >,
104
105 // by frequency (LFU)
106 boost::multi_index::ordered_non_unique<
107 boost::multi_index::tag<byFrequency>,
108 boost::multi_index::member<CleanupEntry, uint64_t, &CleanupEntry::frequency>,
109 std::less<uint64_t>
110 >
111
112 >
113 > CleanupIndex;
114
115 CleanupIndex m_cleanupIndex;
116};
117
118} // namespace util
119} // namespace ndn
120
121#endif // NDN_UTIL_IN_MEMORY_STORAGE_LFU_HPP