1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
|
#pragma once
#include "base/assert.hpp"
#include <cstddef>
#include <functional>
#include <map>
#include <unordered_map>
/// \brief Implementation of cache with least recently used replacement policy.
template <typename Key, typename Value>
class LruCache
{
template <typename K, typename V> friend class LruCacheTest;
template <typename K, typename V> friend class LruCacheKeyAgeTest;
public:
/// \param maxCacheSize Maximum size of the cache in number of items. It should be one or greater.
/// \param loader Function which is called if it's necessary to load a new item for the cache.
/// For the same |key| should be loaded the same |value|.
explicit LruCache(size_t maxCacheSize) : m_maxCacheSize(maxCacheSize)
{
CHECK_GREATER(maxCacheSize, 0, ());
}
// Find value by @key. If @key is found, returns reference to its value.
Value & Find(Key const & key, bool & found)
{
auto const it = m_cache.find(key);
if (it != m_cache.cend())
{
m_keyAge.UpdateAge(key);
found = true;
return it->second;
}
if (m_cache.size() >= m_maxCacheSize)
{
m_cache.erase(m_keyAge.GetLruKey());
m_keyAge.RemoveLru();
}
m_keyAge.InsertKey(key);
Value & value = m_cache[key];
found = false;
return value;
}
/// \brief Checks for coherence class params.
/// \note It's a time consumption method and should be called for tests only.
bool IsValidForTesting() const
{
if (!m_keyAge.IsValidForTesting())
return false;
for (auto const & kv : m_cache)
{
if (!m_keyAge.IsKeyValidForTesting(kv.first))
return false;
}
return true;
}
private:
/// \brief This class support cross mapping from age to key and for key to age.
/// It lets effectively get least recently used key (key with minimum value of age)
/// and find key age by its value to update the key age.
/// \note Size of |m_ageToKey| and |m_ageToKey| should be the same.
/// All keys of |m_ageToKey| should be values of |m_ageToKey| and on the contrary
/// all keys of |m_ageToKey| should be values of |m_ageToKey|.
/// \note Ages should be unique for all keys.
class KeyAge
{
template <typename K, typename V> friend class LruCacheKeyAgeTest;
public:
/// \brief Increments |m_age| and insert key to |m_ageToKey| and |m_keyToAge|.
/// \note This method should be used only if there's no |key| in |m_ageToKey| and |m_keyToAge|.
void InsertKey(Key const & key)
{
++m_age;
m_ageToKey[m_age] = key;
m_keyToAge[key] = m_age;
}
/// \brief Increments |m_age| and updates key age in |m_ageToKey| and |m_keyToAge|.
/// \note This method should be used only if there's |key| in |m_ageToKey| and |m_keyToAge|.
void UpdateAge(Key const & key)
{
++m_age;
auto keyToAgeIt = m_keyToAge.find(key);
CHECK(keyToAgeIt != m_keyToAge.end(), ());
// Removing former age.
size_t const removed = m_ageToKey.erase(keyToAgeIt->second);
CHECK_EQUAL(removed, 1, ());
// Putting new age.
m_ageToKey[m_age] = key;
keyToAgeIt->second = m_age;
}
/// \returns Least recently used key without updating the age.
/// \note |m_ageToKey| and |m_keyToAge| shouldn't be empty.
Key const & GetLruKey() const
{
CHECK(!m_ageToKey.empty(), ());
// The smaller age the older item.
return m_ageToKey.cbegin()->second;
}
void RemoveLru()
{
Key const & lru = GetLruKey();
size_t const removed = m_keyToAge.erase(lru);
CHECK_EQUAL(removed, 1, ());
m_ageToKey.erase(m_ageToKey.begin());
}
/// \brief Checks for coherence class params.
/// \note It's a time consumption method and should be called for tests only.
bool IsValidForTesting() const
{
for (auto const & kv : m_ageToKey)
{
if (kv.first > m_age)
return false;
if (m_keyToAge.find(kv.second) == m_keyToAge.cend())
return false;
}
for (auto const & kv : m_keyToAge)
{
if (kv.second > m_age)
return false;
if (m_ageToKey.find(kv.second) == m_ageToKey.cend())
return false;
}
return true;
}
/// \returns true if |key| and its age are contained in |m_keyToAge| and |m_keyToAge|.
/// \note It's a time consumption method and should be called for tests only.
bool IsKeyValidForTesting(Key const & key) const
{
auto const keyToAgeId = m_keyToAge.find(key);
if (keyToAgeId == m_keyToAge.cend())
return false;
auto const ageToKeyIt = m_ageToKey.find(keyToAgeId->second);
if (ageToKeyIt == m_ageToKey.cend())
return false;
return key == ageToKeyIt->second;
}
private:
size_t m_age = 0;
std::map<size_t, Key> m_ageToKey;
std::unordered_map<Key, size_t> m_keyToAge;
};
size_t const m_maxCacheSize;
std::unordered_map<Key, Value> m_cache;
KeyAge m_keyAge;
};
|
