19#ifndef LIB_QUENTIER_UTILITY_LRU_CACHE_HPP
20#define LIB_QUENTIER_UTILITY_LRU_CACHE_HPP
30 class Key,
class Value,
31 class Allocator = std::allocator<std::pair<Key, Value>>>
35 LRUCache(
const size_t maxSize = 100) :
36 m_container(), m_currentSize(0), m_maxSize(maxSize), m_mapper()
40 using mapped_type = Value;
41 using allocator_type = Allocator;
42 using value_type = std::pair<key_type, mapped_type>;
43 using container_type = std::list<value_type, allocator_type>;
44 using size_type =
typename container_type::size_type;
45 using difference_type =
typename container_type::difference_type;
46 using iterator =
typename container_type::iterator;
47 using const_iterator =
typename container_type::const_iterator;
48 using reverse_iterator = std::reverse_iterator<iterator>;
49 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
51 using reference = value_type &;
52 using const_reference =
const value_type &;
53 using pointer =
typename std::allocator_traits<allocator_type>::pointer;
56 typename std::allocator_traits<allocator_type>::const_pointer;
60 return m_container.begin();
62 const_iterator begin()
const
64 return m_container.begin();
67 reverse_iterator rbegin()
69 return m_container.rbegin();
71 const_reverse_iterator rbegin()
const
73 return m_container.rbegin();
78 return m_container.end();
80 const_iterator end()
const
82 return m_container.end();
85 reverse_iterator rend()
87 return m_container.rend();
89 const_reverse_iterator rend()
const
91 return m_container.rend();
96 return m_container.empty();
100 return m_currentSize;
102 size_t max_size()
const
114 void put(
const key_type & key,
const mapped_type & value)
116 Q_UNUSED(remove(key))
118 m_container.push_front(value_type(key, value));
119 m_mapper[key] = m_container.begin();
125 const mapped_type * get(
const key_type & key)
const
127 auto mapperIt = m_mapper.find(key);
128 if (mapperIt == m_mapper.end()) {
132 auto it = mapperIt.value();
133 if (it == m_container.end()) {
137 m_container.splice(m_container.begin(), m_container, it);
138 mapperIt.value() = m_container.begin();
139 return &(mapperIt.value()->second);
142 bool exists(
const key_type & key)
144 auto mapperIt = m_mapper.find(key);
145 if (mapperIt == m_mapper.end()) {
149 auto it = mapperIt.value();
150 return (it != m_container.end());
153 bool remove(
const key_type & key)
155 auto mapperIt = m_mapper.find(key);
156 if (mapperIt == m_mapper.end()) {
160 auto it = mapperIt.value();
161 Q_UNUSED(m_container.erase(it))
162 Q_UNUSED(m_mapper.erase(mapperIt))
164 if (m_currentSize != 0) {
171 void setMaxSize(
const size_t maxSize)
173 if (maxSize >= m_maxSize) {
178 size_t diff = m_maxSize - maxSize;
179 for (
size_t i = 0; (i < diff) && !m_container.empty(); ++i) {
180 auto lastIt = m_container.end();
183 const key_type & lastElementKey = lastIt->first;
184 Q_UNUSED(m_mapper.remove(lastElementKey))
185 Q_UNUSED(m_container.erase(lastIt))
187 if (m_currentSize != 0) {
196 if (m_currentSize <= m_maxSize) {
200 if (Q_UNLIKELY(m_container.empty())) {
204 auto lastIt = m_container.end();
207 const key_type & lastElementKey = lastIt->first;
209 Q_UNUSED(m_mapper.remove(lastElementKey))
210 Q_UNUSED(m_container.erase(lastIt))
212 if (m_currentSize != 0) {
218 mutable container_type m_container;
219 size_t m_currentSize;
222 mutable QHash<Key, iterator> m_mapper;
Definition LRUCache.hpp:33