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
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
|
/**
* Copyright (C) 2013 10gen Inc.
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU Affero General Public License, version 3,
* as published by the Free Software Foundation.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU Affero General Public License for more details.
*
* You should have received a copy of the GNU Affero General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*
* As a special exception, the copyright holders give permission to link the
* code of portions of this program with the OpenSSL library under certain
* conditions as described in each individual source file and distribute
* linked combinations including the program with the OpenSSL library. You
* must comply with the GNU Affero General Public License in all respects for
* all of the code used other than as permitted herein. If you modify file(s)
* with this exception, you may extend this exception to your version of the
* file(s), but you are not obligated to do so. If you do not wish to do so,
* delete this exception statement from your version. If you delete this
* exception statement from all source files in the program, then also delete
* it in the license file.
*/
#pragma once
#include <list>
#include <memory>
#include "mongo/base/status.h"
#include "mongo/stdx/unordered_map.h"
#include "mongo/util/assert_util.h"
namespace mongo {
/**
* A key-value store structure with a least recently used (LRU) replacement
* policy. The number of entries allowed in the kv-store is set as a constant
* upon construction.
*
* Caveat:
* This kv-store is NOT thread safe! The client to this utility is responsible
* for protecting concurrent access to the LRU store if used in a threaded
* context.
*
* Implemented as a doubly-linked list with a hash map for quickly locating the kv-store entries.
* The add(), get(), and remove() operations are all O(1).
*
* The keys of generic type K map to values of type V*. The V*
* pointers are owned by the kv-store.
*
* TODO: We could move this into the util/ directory and do any cleanup necessary to make it
* fully general.
*/
template <class K, class V>
class LRUKeyValue {
public:
LRUKeyValue(size_t maxSize) : _maxSize(maxSize), _currentSize(0){};
~LRUKeyValue() {
clear();
}
typedef std::pair<K, V*> KVListEntry;
typedef std::list<KVListEntry> KVList;
typedef typename KVList::iterator KVListIt;
typedef typename KVList::const_iterator KVListConstIt;
typedef stdx::unordered_map<K, KVListIt> KVMap;
typedef typename KVMap::const_iterator KVMapConstIt;
/**
* Add an (K, V*) pair to the store, where 'key' can
* be used to retrieve value 'entry' from the store.
*
* Takes ownership of 'entry'.
*
* If 'key' already exists in the kv-store, 'entry' will
* simply replace what is already there.
*
* The least recently used entry is evicted if the
* kv-store is full prior to the add() operation.
*
* If an entry is evicted, it will be returned in
* an unique_ptr for the caller to use before disposing.
*/
std::unique_ptr<V> add(const K& key, V* entry) {
// If the key already exists, delete it first.
KVMapConstIt i = _kvMap.find(key);
if (i != _kvMap.end()) {
KVListIt found = i->second;
delete found->second;
_kvMap.erase(i);
_kvList.erase(found);
_currentSize--;
}
_kvList.push_front(std::make_pair(key, entry));
_kvMap[key] = _kvList.begin();
_currentSize++;
// If the store has grown beyond its allowed size,
// evict the least recently used entry.
if (_currentSize > _maxSize) {
V* evictedEntry = _kvList.back().second;
invariant(evictedEntry);
_kvMap.erase(_kvList.back().first);
_kvList.pop_back();
_currentSize--;
invariant(_currentSize == _maxSize);
// Pass ownership of evicted entry to caller.
// If caller chooses to ignore this unique_ptr,
// the evicted entry will be deleted automatically.
return std::unique_ptr<V>(evictedEntry);
}
return std::unique_ptr<V>();
}
/**
* Retrieve the value associated with 'key' from
* the kv-store. The value is returned through the
* out-parameter 'entryOut'.
*
* The kv-store retains ownership of 'entryOut', so
* it should not be deleted by the caller.
*
* As a side effect, the retrieved entry is promoted
* to the most recently used.
*/
Status get(const K& key, V** entryOut) const {
KVMapConstIt i = _kvMap.find(key);
if (i == _kvMap.end()) {
return Status(ErrorCodes::NoSuchKey, "no such key in LRU key-value store");
}
KVListIt found = i->second;
V* foundEntry = found->second;
// Promote the kv-store entry to the front of the list.
// It is now the most recently used.
_kvMap.erase(i);
_kvList.erase(found);
_kvList.push_front(std::make_pair(key, foundEntry));
_kvMap[key] = _kvList.begin();
*entryOut = foundEntry;
return Status::OK();
}
/**
* Remove the kv-store entry keyed by 'key'.
*/
Status remove(const K& key) {
KVMapConstIt i = _kvMap.find(key);
if (i == _kvMap.end()) {
return Status(ErrorCodes::NoSuchKey, "no such key in LRU key-value store");
}
KVListIt found = i->second;
delete found->second;
_kvMap.erase(i);
_kvList.erase(found);
_currentSize--;
return Status::OK();
}
/**
* Deletes all entries in the kv-store.
*/
void clear() {
for (KVListIt i = _kvList.begin(); i != _kvList.end(); i++) {
delete i->second;
}
_kvList.clear();
_kvMap.clear();
_currentSize = 0;
}
/**
* Returns true if entry is found in the kv-store.
*/
bool hasKey(const K& key) const {
return _kvMap.find(key) != _kvMap.end();
}
/**
* Returns the number of entries currently in the kv-store.
*/
size_t size() const {
return _currentSize;
}
/**
* TODO: The kv-store should implement its own iterator. Calling through to the underlying
* iterator exposes the internals, and forces the caller to make a horrible type
* declaration.
*/
KVListConstIt begin() const {
return _kvList.begin();
}
KVListConstIt end() const {
return _kvList.end();
}
private:
// The maximum allowable number of entries in the kv-store.
const size_t _maxSize;
// The number of entries currently in the kv-store.
size_t _currentSize;
// (K, V*) pairs are stored in this std::list. They are sorted in order
// of use, where the front is the most recently used and the back is the
// least recently used.
mutable KVList _kvList;
// Maps from a key to the corresponding std::list entry.
mutable KVMap _kvMap;
};
} // namespace mongo
|
