libquentier  0.4.0
The library for rich desktop clients of Evernote service
LRUCache.hpp
1 /*
2  * Copyright 2016 Dmitry Ivanov
3  *
4  * This file is part of libquentier
5  *
6  * libquentier is free software; you can redistribute it and/or modify
7  * it under the terms of the GNU Lesser General Public License as published by
8  * the Free Software Foundation, version 3 of the License.
9  *
10  * libquentier is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13  * GNU Lesser General Public License for more details.
14  *
15  * You should have received a copy of the GNU Lesser General Public License
16  * along with libquentier. If not, see <http://www.gnu.org/licenses/>.
17  */
18 
19 #ifndef LIB_QUENTIER_UTILITY_LRU_CACHE_HPP
20 #define LIB_QUENTIER_UTILITY_LRU_CACHE_HPP
21 
22 #include <quentier/utility/Macros.h>
23 #include <list>
24 #include <cstddef>
25 #include <QHash>
26 
27 namespace quentier {
28 
29 template<class Key, class Value, class Allocator = std::allocator<std::pair<Key, Value> > >
30 class LRUCache
31 {
32 public:
33  LRUCache(const size_t maxSize = 100) :
34  m_container(),
35  m_currentSize(0),
36  m_maxSize(maxSize),
37  m_mapper()
38  {}
39 
40  typedef Key key_type;
41  typedef Value mapped_type;
42  typedef Allocator allocator_type;
43  typedef std::pair<key_type, mapped_type> value_type;
44  typedef std::list<value_type, allocator_type> container_type;
45  typedef typename container_type::size_type size_type;
46  typedef typename container_type::difference_type difference_type;
47  typedef typename container_type::iterator iterator;
48  typedef typename container_type::const_iterator const_iterator;
49  typedef std::reverse_iterator<iterator> reverse_iterator;
50  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
51 
52 #if __cplusplus < 201103L
53  typedef typename allocator_type::reference reference;
54  typedef typename allocator_type::const_reference const_reference;
55  typedef typename allocator_type::pointer pointer;
56  typedef typename allocator_type::const_pointer const_pointer;
57 #else
58  typedef value_type& reference;
59  typedef const value_type& const_reference;
60  typedef typename std::allocator_traits<allocator_type>::pointer pointer;
61  typedef typename std::allocator_traits<allocator_type>::const_pointer const_pointer;
62 #endif
63 
64  iterator begin() { return m_container.begin(); }
65  const_iterator begin() const { return m_container.begin(); }
66 
67  reverse_iterator rbegin() { return m_container.rbegin(); }
68  const_reverse_iterator rbegin() const { return m_container.rbegin(); }
69 
70  iterator end() { return m_container.end(); }
71  const_iterator end() const { return m_container.end(); }
72 
73  reverse_iterator rend() { return m_container.rend(); }
74  const_reverse_iterator rend() const { return m_container.rend(); }
75 
76  bool empty() const { return m_container.empty(); }
77  size_t size() const { return m_currentSize; }
78  size_t max_size() const { return m_maxSize; }
79 
80  void clear() { m_container.clear(); m_mapper.clear(); m_currentSize = 0; }
81 
82  void put(const key_type & key, const mapped_type & value)
83  {
84  auto mapperIt = m_mapper.find(key);
85  if (mapperIt != m_mapper.end()) {
86  auto it = mapperIt.value();
87  Q_UNUSED(m_container.erase(it))
88  Q_UNUSED(m_mapper.erase(mapperIt))
89  if (m_currentSize != 0) {
90  --m_currentSize;
91  }
92  }
93 
94  m_container.push_front(value_type(key, value));
95  m_mapper[key] = m_container.begin();
96  ++m_currentSize;
97 
98  if (m_currentSize > m_maxSize)
99  {
100  auto lastIt = m_container.end();
101  --lastIt;
102 
103  const key_type & lastElementKey = lastIt->first;
104 
105  Q_UNUSED(m_mapper.remove(lastElementKey))
106  Q_UNUSED(m_container.erase(lastIt))
107 
108  if (m_currentSize != 0) {
109  --m_currentSize;
110  }
111  }
112  }
113 
114  const mapped_type * get(const key_type & key) const
115  {
116  auto mapperIt = m_mapper.find(key);
117  if (mapperIt == m_mapper.end()) {
118  return Q_NULLPTR;
119  }
120 
121  auto it = mapperIt.value();
122  m_container.splice(m_container.begin(), m_container, it);
123  mapperIt.value() = m_container.begin();
124  return &(mapperIt.value()->second);
125  }
126 
127  bool exists(const key_type & key)
128  {
129  auto mapperIt = m_mapper.find(key);
130  return (mapperIt != m_mapper.end());
131  }
132 
133  bool remove(const key_type & key)
134  {
135  auto mapperIt = m_mapper.find(key);
136  if (mapperIt == m_mapper.end()) {
137  return false;
138  }
139 
140  auto it = mapperIt.value();
141  Q_UNUSED(m_container.erase(it))
142  Q_UNUSED(m_mapper.erase(mapperIt))
143  if (m_currentSize != 0) {
144  --m_currentSize;
145  }
146 
147  return true;
148  }
149 
150 private:
151  mutable container_type m_container;
152  size_t m_currentSize;
153  size_t m_maxSize;
154 
155  mutable QHash<Key, iterator> m_mapper;
156 };
157 
158 } // namespace quentier
159 
160 #endif // LIB_QUENTIER_UTILITY_LRU_CACHE_HPP
Definition: LRUCache.hpp:30