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
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
|
/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
/*
* This file is part of the LibreOffice project.
*
* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/.
*
*/
#ifndef INCLUDED_O3TL_LRU_MAP_HXX
#define INCLUDED_O3TL_LRU_MAP_HXX
#include <algorithm>
#include <cassert>
#include <list>
#include <unordered_map>
#include <cstddef>
namespace o3tl
{
/** LRU map
*
* Similar to unordered_map (it actually uses it) with additionally functionality
* which removes the entries that have been "least recently used" when the size
* hits the specified capacity.
*
* It only implements the minimal methods needed and the implementation is NOT
* thread safe.
*
* The implementation is as simple as possible but it still uses O(1) complexity
* for most of the operations with a combination unordered map and linked list.
*
**/
template<typename Key, typename Value, class KeyHash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
class lru_map final
{
public:
typedef typename std::pair<Key, Value> key_value_pair_t;
private:
typedef std::list<key_value_pair_t> list_t;
typedef typename list_t::iterator list_iterator_t;
typedef typename list_t::const_iterator list_const_iterator_t;
typedef std::unordered_map<Key, list_iterator_t, KeyHash, KeyEqual> map_t;
typedef typename map_t::iterator map_iterator_t;
typedef typename map_t::const_iterator map_const_iterator_t;
list_t mLruList;
map_t mLruMap;
const size_t mMaxSize;
void checkLRU()
{
if (mLruMap.size() > mMaxSize)
{
// remove from map
mLruMap.erase(mLruList.back().first);
// remove from list
mLruList.pop_back();
}
}
public:
typedef list_iterator_t iterator;
typedef list_const_iterator_t const_iterator;
// a size of 0 effectively disables the LRU cleanup code
lru_map(size_t nMaxSize)
: mMaxSize(nMaxSize ? nMaxSize : std::min(mLruMap.max_size(), mLruList.max_size()))
{}
~lru_map()
{
// Some code .e.g. SalBitmap likes to remove itself from a cache during it's destructor, which means we
// get calls into lru_map while we are in destruction, so use the swap-and-clear idiom to avoid those problems.
mLruMap.clear();
list_t aLruListTemp;
aLruListTemp.swap(mLruList);
}
void insert(key_value_pair_t& rPair)
{
map_iterator_t i = mLruMap.find(rPair.first);
if (i == mLruMap.end()) // doesn't exist -> add to queue and map
{
// add to front of the list
mLruList.push_front(rPair);
// add the list position (iterator) to the map
auto it = mLruList.begin();
mLruMap[it->first] = it;
checkLRU();
}
else // already exists -> replace value
{
// replace value
i->second->second = rPair.second;
// bring to front of the lru list
mLruList.splice(mLruList.begin(), mLruList, i->second);
}
}
void insert(key_value_pair_t&& rPair)
{
map_iterator_t i = mLruMap.find(rPair.first);
if (i == mLruMap.end()) // doesn't exist -> add to list and map
{
// add to front of the list
mLruList.push_front(std::move(rPair));
// add the list position (iterator) to the map
auto it = mLruList.begin();
mLruMap[it->first] = it;
checkLRU();
}
else // already exists -> replace value
{
// replace value
i->second->second = std::move(rPair.second);
// push to back of the lru list
mLruList.splice(mLruList.begin(), mLruList, i->second);
}
}
list_const_iterator_t find(const Key& key)
{
const map_iterator_t i = mLruMap.find(key);
if (i == mLruMap.cend()) // can't find entry for the key
{
// return empty iterator
return mLruList.cend();
}
else
{
// push to back of the lru list
mLruList.splice(mLruList.begin(), mLruList, i->second);
return i->second;
}
}
// reverse-iterates the list removing all items matching the predicate
template<class UnaryPredicate>
void remove_if(UnaryPredicate pred)
{
auto it = mLruList.rbegin();
while (it != mLruList.rend())
{
if (pred(*it))
{
mLruMap.erase(it->first);
it = decltype(it){ mLruList.erase(std::next(it).base()) };
}
else
++it;
}
}
list_const_iterator_t begin() const
{
return mLruList.cbegin();
}
list_const_iterator_t end() const
{
return mLruList.cend();
}
size_t size() const
{
assert(mLruMap.size() == mLruList.size());
return mLruMap.size();
}
void clear()
{
mLruMap.clear();
mLruList.clear();
}
};
}
#endif /* INCLUDED_O3TL_LRU_MAP_HXX */
/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
