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
|
// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
// vim: ts=8 sw=2 smarttab
#pragma once
#include <memory>
#include <optional>
#include <boost/smart_ptr/local_shared_ptr.hpp>
#include <boost/smart_ptr/weak_ptr.hpp>
#include "simple_lru.h"
/// SharedLRU does its best to cache objects. It not only tracks the objects
/// in its LRU cache with strong references, it also tracks objects with
/// weak_ptr even if the cache does not hold any strong references to them. so
/// that it can return the objects after they are evicted, as long as they've
/// ever been cached and have not been destroyed yet.
template<class K, class V>
class SharedLRU {
using shared_ptr_t = boost::local_shared_ptr<V>;
using weak_ptr_t = boost::weak_ptr<V>;
using value_type = std::pair<K, shared_ptr_t>;
// weak_refs is already ordered, and we don't use accessors like
// LRUCache::lower_bound(), so unordered LRUCache would suffice.
SimpleLRU<K, shared_ptr_t, false> cache;
std::map<K, std::pair<weak_ptr_t, V*>> weak_refs;
struct Deleter {
SharedLRU<K,V>* cache;
const K key;
void operator()(V* ptr) {
cache->_erase_weak(key);
delete ptr;
}
};
void _erase_weak(const K& key) {
weak_refs.erase(key);
}
public:
SharedLRU(size_t max_size = 20)
: cache{max_size}
{}
~SharedLRU() {
cache.clear();
// use plain assert() in utiliy classes to avoid dependencies on logging
assert(weak_refs.empty());
}
/**
* Returns a reference to the given key, and perform an insertion if such
* key does not already exist
*/
shared_ptr_t operator[](const K& key);
/**
* Returns true iff there are no live references left to anything that has been
* in the cache.
*/
bool empty() const {
return weak_refs.empty();
}
size_t size() const {
return cache.size();
}
size_t capacity() const {
return cache.capacity();
}
/***
* Inserts a key if not present, or bumps it to the front of the LRU if
* it is, and then gives you a reference to the value. If the key already
* existed, you are responsible for deleting the new value you tried to
* insert.
*
* @param key The key to insert
* @param value The value that goes with the key
* @param existed Set to true if the value was already in the
* map, false otherwise
* @return A reference to the map's value for the given key
*/
shared_ptr_t insert(const K& key, std::unique_ptr<V> value);
// clear all strong reference from the lru.
void clear() {
cache.clear();
}
shared_ptr_t find(const K& key);
// return the last element that is not greater than key
shared_ptr_t lower_bound(const K& key);
// return the first element that is greater than key
std::optional<value_type> upper_bound(const K& key);
void erase(const K& key) {
cache.erase(key);
_erase_weak(key);
}
};
template<class K, class V>
typename SharedLRU<K,V>::shared_ptr_t
SharedLRU<K,V>::insert(const K& key, std::unique_ptr<V> value)
{
shared_ptr_t val;
if (auto found = weak_refs.find(key); found != weak_refs.end()) {
val = found->second.first.lock();
}
if (!val) {
val.reset(value.release(), Deleter{this, key});
weak_refs.emplace(key, std::make_pair(val, val.get()));
}
cache.insert(key, val);
return val;
}
template<class K, class V>
typename SharedLRU<K,V>::shared_ptr_t
SharedLRU<K,V>::operator[](const K& key)
{
if (auto found = cache.find(key); found) {
return *found;
}
shared_ptr_t val;
if (auto found = weak_refs.find(key); found != weak_refs.end()) {
val = found->second.first.lock();
}
if (!val) {
val.reset(new V{}, Deleter{this, key});
weak_refs.emplace(key, std::make_pair(val, val.get()));
}
cache.insert(key, val);
return val;
}
template<class K, class V>
typename SharedLRU<K,V>::shared_ptr_t
SharedLRU<K,V>::find(const K& key)
{
if (auto found = cache.find(key); found) {
return *found;
}
shared_ptr_t val;
if (auto found = weak_refs.find(key); found != weak_refs.end()) {
val = found->second.first.lock();
}
if (val) {
cache.insert(key, val);
}
return val;
}
template<class K, class V>
typename SharedLRU<K,V>::shared_ptr_t
SharedLRU<K,V>::lower_bound(const K& key)
{
if (weak_refs.empty()) {
return {};
}
auto found = weak_refs.lower_bound(key);
if (found == weak_refs.end()) {
--found;
}
if (auto val = found->second.first.lock(); val) {
cache.insert(key, val);
return val;
} else {
return {};
}
}
template<class K, class V>
std::optional<typename SharedLRU<K,V>::value_type>
SharedLRU<K,V>::upper_bound(const K& key)
{
for (auto found = weak_refs.upper_bound(key);
found != weak_refs.end();
++found) {
if (auto val = found->second.first.lock(); val) {
return std::make_pair(found->first, val);
}
}
return std::nullopt;
}
|
