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
|
/*
* Copyright 2016 Google Inc.
*
* Use of this source code is governed by a BSD-style license that can be
* found in the LICENSE file.
*/
#ifndef SkLRUCache_DEFINED
#define SkLRUCache_DEFINED
#include "include/private/SkChecksum.h"
#include "src/base/SkTInternalLList.h"
#include "src/core/SkTHash.h"
/**
* A generic LRU cache.
*/
template <typename K, typename V, typename HashK = SkGoodHash>
class SkLRUCache {
private:
struct Entry {
Entry(const K& key, V&& value)
: fKey(key)
, fValue(std::move(value)) {}
K fKey;
V fValue;
SK_DECLARE_INTERNAL_LLIST_INTERFACE(Entry);
};
public:
explicit SkLRUCache(int maxCount) : fMaxCount(maxCount) {}
SkLRUCache() = delete;
~SkLRUCache() {
Entry* node = fLRU.head();
while (node) {
fLRU.remove(node);
delete node;
node = fLRU.head();
}
}
// Make noncopyable
SkLRUCache(const SkLRUCache&) = delete;
SkLRUCache& operator=(const SkLRUCache&) = delete;
V* find(const K& key) {
Entry** value = fMap.find(key);
if (!value) {
return nullptr;
}
Entry* entry = *value;
if (entry != fLRU.head()) {
fLRU.remove(entry);
fLRU.addToHead(entry);
} // else it's already at head position, don't need to do anything
return &entry->fValue;
}
V* insert(const K& key, V value) {
SkASSERT(!this->find(key));
Entry* entry = new Entry(key, std::move(value));
fMap.set(entry);
fLRU.addToHead(entry);
while (fMap.count() > fMaxCount) {
this->remove(fLRU.tail()->fKey);
}
return &entry->fValue;
}
V* insert_or_update(const K& key, V value) {
if (V* found = this->find(key)) {
*found = std::move(value);
return found;
} else {
return this->insert(key, std::move(value));
}
}
int count() const {
return fMap.count();
}
template <typename Fn> // f(K*, V*)
void foreach(Fn&& fn) {
typename SkTInternalLList<Entry>::Iter iter;
for (Entry* e = iter.init(fLRU, SkTInternalLList<Entry>::Iter::kHead_IterStart); e;
e = iter.next()) {
fn(&e->fKey, &e->fValue);
}
}
void reset() {
fMap.reset();
for (Entry* e = fLRU.head(); e; e = fLRU.head()) {
fLRU.remove(e);
delete e;
}
}
private:
struct Traits {
static const K& GetKey(Entry* e) {
return e->fKey;
}
static uint32_t Hash(const K& k) {
return HashK()(k);
}
};
void remove(const K& key) {
Entry** value = fMap.find(key);
SkASSERT(value);
Entry* entry = *value;
SkASSERT(key == entry->fKey);
fMap.remove(key);
fLRU.remove(entry);
delete entry;
}
int fMaxCount;
SkTHashTable<Entry*, K, Traits> fMap;
SkTInternalLList<Entry> fLRU;
};
#endif
|
