in-memory-storage-lfu.hpp
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2013-2021 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_CXX_IMS_IN_MEMORY_STORAGE_LFU_HPP
23 #define NDN_CXX_IMS_IN_MEMORY_STORAGE_LFU_HPP
24 
26 
27 #include <boost/multi_index_container.hpp>
28 #include <boost/multi_index/hashed_index.hpp>
29 #include <boost/multi_index/identity.hpp>
30 #include <boost/multi_index/member.hpp>
31 #include <boost/multi_index/ordered_index.hpp>
32 
33 namespace ndn {
34 
40 {
41 public:
42  explicit
43  InMemoryStorageLfu(size_t limit = 16);
44 
45  explicit
46  InMemoryStorageLfu(boost::asio::io_service& ioService, size_t limit = 16);
47 
53  bool
54  evictItem() override;
55 
59  void
60  afterAccess(InMemoryStorageEntry* entry) override;
61 
64  void
65  afterInsert(InMemoryStorageEntry* entry) override;
66 
70  void
71  beforeErase(InMemoryStorageEntry* entry) override;
72 
73 private:
74  // binds frequency and entry together
75  struct CleanupEntry
76  {
77  InMemoryStorageEntry* entry;
78  uint64_t frequency; // could potentially be overflowed
79  };
80 
83  static inline void
84  incrementFrequency(CleanupEntry& cleanupEntry)
85  {
86  ++cleanupEntry.frequency;
87  }
88 
89 private:
90  // multi_index_container to implement LFU
91  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 
117 } // namespace ndn
118 
119 #endif // NDN_CXX_IMS_IN_MEMORY_STORAGE_LFU_HPP
Represents an in-memory storage entry.
Provides an in-memory storage with Least Frequently Used (LFU) replacement policy.
void afterAccess(InMemoryStorageEntry *entry) override
Update the entry when the entry is returned by the find() function, increment the frequency according...
void beforeErase(InMemoryStorageEntry *entry) override
Update the entry or other data structures before a entry is successfully erased, erase it from the cl...
void afterInsert(InMemoryStorageEntry *entry) override
Update the entry after a entry is successfully inserted, add it to the cleanupIndex.
bool evictItem() override
Removes one Data packet from in-memory storage based on LFU, i.e.
Represents in-memory storage.
#define NDN_CXX_PUBLIC_WITH_TESTS_ELSE_PROTECTED
Definition: common.hpp:47
Definition: data.cpp:25