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
|
// Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
#pragma once
#include <vespa/vespalib/stllike/hashtable.h>
#include <vespa/vespalib/stllike/hash_fun.h>
#include <vespa/vespalib/stllike/select.h>
#include <vector>
namespace vespalib {
struct LinkedValueBase {
static const uint32_t npos = static_cast<uint32_t>(-1);
LinkedValueBase() : _prev(npos), _next(npos) { }
LinkedValueBase(uint32_t prev, uint32_t next) : _prev(prev), _next(next) { }
uint32_t _prev;
uint32_t _next;
};
template<typename V>
struct LinkedValue : public LinkedValueBase
{
LinkedValue() {}
LinkedValue(const V & v) : LinkedValueBase(), _value(v) { }
LinkedValue(V && v) : LinkedValueBase(), _value(std::move(v)) { }
V _value;
};
template<typename K, typename V, typename H = vespalib::hash<K>, typename EQ = std::equal_to<K> >
struct LruParam
{
typedef LinkedValue<V> LV;
typedef std::pair< K, LV > value_type;
typedef vespalib::Select1st< value_type > select_key;
typedef K Key;
typedef V Value;
typedef H Hash;
typedef EQ Equal;
typedef hashtable< Key, value_type, Hash, Equal, select_key > HashTable;
};
template< typename P >
class lrucache_map : private P::HashTable
{
private:
typedef typename P::HashTable HashTable;
typedef typename P::Value V;
typedef typename P::Key K;
typedef typename P::value_type value_type;
typedef typename P::LV LV;
typedef typename HashTable::iterator internal_iterator;
typedef typename HashTable::next_t next_t;
typedef typename HashTable::NodeStore NodeStore;
protected:
static constexpr size_t UNLIMITED = std::numeric_limits<size_t>::max();
public:
typedef typename HashTable::insert_result insert_result;
class iterator {
public:
iterator(lrucache_map * cache, uint32_t current) : _cache(cache), _current(current) { }
V & operator * () const { return _cache->getByInternalIndex(_current).second._value; }
V * operator -> () const { return & _cache->getByInternalIndex(_current).second._value; }
iterator & operator ++ () {
if (_current != LinkedValueBase::npos) {
_current = _cache->getByInternalIndex(_current).second._next;
}
return *this;
}
iterator operator ++ (int) {
iterator prev = *this;
++(*this);
return prev;
}
bool operator==(const iterator& rhs) const { return (_current == rhs._current); }
bool operator!=(const iterator& rhs) const { return (_current != rhs._current); }
private:
lrucache_map * _cache;
uint32_t _current;
friend class lrucache_map;
};
/**
* Will create a lrucache with max elements. Use the chained setter
* @ref reserve to control initial size.
*
* @param maxElements in cache unless you override @ref removeOldest.
*/
lrucache_map(size_t maxElems);
virtual ~lrucache_map();
lrucache_map & maxElements(size_t elems) {
_maxElements = elems;
return *this;
}
lrucache_map & reserve(size_t elems) {
HashTable::reserve(elems);
return *this;
}
size_t capacity() const { return _maxElements; }
size_t size() const { return HashTable::size(); }
bool empty() const { return HashTable::empty(); }
iterator begin() { return iterator(this, _head); }
iterator end() { return iterator(this, LinkedValueBase::npos); }
/**
* This fetches the object without modifying the lru list.
*/
const V & get(const K & key) { return HashTable::find(key)->second._value; }
/**
* This simply erases the object.
*/
void erase(const K & key);
/**
* Erase object pointed to by iterator.
*/
iterator erase(const iterator & it);
/**
* Object is inserted in cache with given key.
* Object is then put at head of LRU list.
*/
insert_result insert(const K & key, const V & value);
/**
* Object is inserted in cache with given key.
* Object is then put at head of LRU list.
*/
insert_result insert(const K & key, V && value);
/**
* Return the object with the given key. If it does not exist an empty one will be created.
* This can be used as an insert.
* Object is then put at head of LRU list.
*/
const V & operator [] (const K & key) const {
return const_cast<lrucache_map<P> *>(this)->findAndRef(key).second._value;
}
/**
* Return the object with the given key. If it does not exist an empty one will be created.
* This can be used as an insert.
* Object is then put at head of LRU list.
*/
V & operator [] (const K & key);
/**
* Tell if an object with given key exists in the cache.
* Does not alter the LRU list.
*/
bool hasKey(const K & key) const { return HashTable::find(key) != HashTable::end(); }
/**
* Called when an object is inserted, to see if the LRU should be removed.
* Default is to obey the maxsize given in constructor.
* The obvious extension is when you are storing pointers and want to cap
* on the real size of the object pointed to.
*/
virtual bool removeOldest(const value_type & v);
virtual void onRemove(const K & key);
virtual void onInsert(const K & key);
/**
* Method for testing that internal consitency is good.
*/
bool verifyInternals();
/**
* Implements the move callback from the hashtable
*/
void move(next_t from, next_t to);
void swap(lrucache_map & rhs);
private:
typedef std::pair<uint32_t, uint32_t> MoveRecord;
typedef std::vector<MoveRecord> MoveRecords;
/**
* Implements the resize of the hashtable
*/
void move(NodeStore && oldStore) override;
internal_iterator findAndRef(const K & key);
void ref(const internal_iterator & it);
insert_result insert(value_type && value);
void removeOld();
class RecordMoves {
public:
RecordMoves(const RecordMoves &) = delete;
RecordMoves & operator = (const RecordMoves &) = delete;
RecordMoves(lrucache_map & lru) :
_lru(lru)
{
_lru._moveRecordingEnabled = true;
}
~RecordMoves();
uint32_t movedTo(uint32_t from);
private:
lrucache_map & _lru;
};
size_t _maxElements;
mutable uint32_t _head;
mutable uint32_t _tail;
bool _moveRecordingEnabled;
MoveRecords _moved;
};
}
|
