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
|
// Copyright 2020 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#ifndef THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_LRU_CACHE_H_
#define THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_LRU_CACHE_H_
#include <memory>
#include "third_party/blink/renderer/platform/wtf/allocator/allocator.h"
#include "third_party/blink/renderer/platform/wtf/construct_traits.h"
#include "third_party/blink/renderer/platform/wtf/doubly_linked_list.h"
#include "third_party/blink/renderer/platform/wtf/hash_map.h"
#include "third_party/blink/renderer/platform/wtf/hash_table_deleted_value_type.h"
namespace WTF {
// LruCache is a simple least-recently-used cache based on HashMap and
// DoublyLinkedList. Useful in situations where caching by using a HashMap is
// desirable but needs to be limited in size to not grow out of proportions.
// LruCache uses a HashMap to store cache entries, and uses a DoublyLinkedList
// in parallel to keep track of the age of entries. Accessing an entry using
// Get() refreshes its age, Put() places a new entry into the HashMap with
// youngest age as well. The least recently used entry of the list is pruned
// when a Put() call would otherwise exceed the max_size limit.
//
// Example:
// const size_t kMaxSize = 2;
// LruCache<uint16_t, String> my_cache(kMaxSize);
// my_cache.Put(13, "first string");
// my_cache.Put(42, "second string");
// my_cache.Put(256, "third string");
// my_cache.Get(13) // -> nullptr, has been removed due to kMaxSize == 2.
// my_cache.Get(42) // -> String* "second string"
// my_cache.Get(256) // -> String* "third_string"
//
// See lru_cache_test.cc for more examples.
template <typename KeyArg,
typename MappedArg,
typename HashArg = typename DefaultHash<KeyArg>::Hash,
typename KeyTraitsArg = HashTraits<KeyArg>>
class LruCache {
USING_FAST_MALLOC(LruCache);
private:
class MappedListNodeWithKey final
: public DoublyLinkedListNode<MappedListNodeWithKey> {
USING_FAST_MALLOC(MappedListNodeWithKey);
public:
friend class DoublyLinkedListNode<MappedListNodeWithKey>;
MappedListNodeWithKey(const KeyArg& key, MappedArg&& mapped_arg)
: key_(key), mapped_value_(std::move(mapped_arg)) {}
MappedArg* Value() { return &mapped_value_; }
void SetValue(MappedArg&& mapped_arg) {
mapped_value_ = std::move(mapped_arg);
}
const KeyArg& Key() const { return key_; }
private:
KeyArg key_;
MappedArg mapped_value_;
MappedListNodeWithKey* prev_{nullptr};
MappedListNodeWithKey* next_{nullptr};
};
using MappedListNode = std::unique_ptr<MappedListNodeWithKey>;
using HashMapType = HashMap<KeyArg, MappedListNode, HashArg, KeyTraitsArg>;
public:
LruCache(size_t max_size) : max_size_(max_size) {
static_assert(!IsGarbageCollectedType<KeyArg>::value ||
!IsGarbageCollectedType<MappedArg>::value,
"Cannot use LruCache<> with garbage collected types.");
CHECK_GT(max_size_, 0u);
}
// Retrieve cache entry under |key| if it exists and refresh its age.
// Returns: pointer to cache entry or nullptr if no entry is found for that
// key.
MappedArg* Get(const KeyArg& key) {
if (map_.IsEmpty())
return nullptr;
typename HashMapType::iterator find_result = map_.find(key);
if (find_result == map_.end())
return nullptr;
// Move result to beginning of list.
MappedListNodeWithKey* node = find_result->value.get();
ordering_.Remove(node);
ordering_.Push(node);
return find_result->value->Value();
}
// Place entry in cache as new / youngest. Multiple calls to Put() with an
// identical key but differing MappedArg will override the stored value and
// refresh the age.
void Put(const KeyArg& key, MappedArg&& arg) {
{
typename HashMapType::iterator find_result = map_.find(key);
if (find_result != map_.end()) {
find_result->value->SetValue(std::move(arg));
ordering_.Remove(find_result->value.get());
ordering_.Push(find_result->value.get());
} else {
auto list_node =
std::make_unique<MappedListNodeWithKey>(key, std::move(arg));
typename HashMapType::AddResult add_result =
map_.insert(key, std::move(list_node));
DCHECK(add_result.is_new_entry);
ordering_.Push(add_result.stored_value->value.get());
}
}
if (map_.size() > max_size_) {
RemoveLeastRecentlyUsed();
}
}
// Clear the cache, remove all elements.
void Clear() {
map_.clear();
ordering_.Clear();
}
size_t size() { return map_.size(); }
private:
void RemoveLeastRecentlyUsed() {
MappedListNodeWithKey* tail = ordering_.Tail();
ordering_.Remove(tail);
map_.erase(tail->Key());
}
HashMapType map_;
DoublyLinkedList<MappedListNodeWithKey> ordering_;
size_t max_size_;
};
} // namespace WTF
#endif // THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_LRU_CACHE_H_
|
