| 1 |
#pragma once |
| 2 |
|
| 3 |
#include <algorithm> |
| 4 |
#include <cassert> |
| 5 |
#include <limits> |
| 6 |
#include <memory> |
| 7 |
#include <vector> |
| 8 |
#include <cstdint> |
| 9 |
// Cache that evicts old entries which have not been used recently. Implemented |
| 10 |
// using array/linear search so this works well for small array sizes. |
| 11 |
template<typename TKey, typename TValue> |
| 12 |
struct LruCache |
| 13 |
{ |
| 14 |
explicit LruCache(int max_entries); |
| 15 |
|
| 16 |
// Fetches an entry for |key|. If it does not exist, |allocator| will be |
| 17 |
// invoked to create one. |
| 18 |
template<typename TAllocator> |
| 19 |
TValue Get(TKey const& key, TAllocator allocator); |
| 20 |
// Returns true if there is an entry for |key|. |
| 21 |
bool Has(TKey const& key); |
| 22 |
// Fetches the entry for |filename| and updates it's usage so it is less |
| 23 |
// likely to be evicted. |
| 24 |
bool TryGet(TKey const& key, TValue* dest); |
| 25 |
// TryGetEntry, except the entry is removed from the cache. |
| 26 |
bool TryTake(TKey const& key, TValue* dest); |
| 27 |
// Inserts an entry. Evicts the oldest unused entry if there is no space. |
| 28 |
void Insert(TKey const& key, TValue const& value); |
| 29 |
|
| 30 |
// Call |func| on existing entries. If |func| returns false iteration |
| 31 |
// terminates early. |
| 32 |
template<typename TFunc> |
| 33 |
void IterateValues(TFunc func); |
| 34 |
|
| 35 |
// Empties the cache |
| 36 |
void Clear(void); |
| 37 |
|
| 38 |
private: |
| 39 |
// There is a global score counter, when we access an element we increase |
| 40 |
// its score to the current global value, so it has the highest overall |
| 41 |
// score. This means that the oldest/least recently accessed value has the |
| 42 |
// lowest score. |
| 43 |
// |
| 44 |
// There is a bit of special logic to handle score overlow. |
| 45 |
struct Entry |
| 46 |
{ |
| 47 |
uint32_t score = 0; |
| 48 |
TKey key; |
| 49 |
TValue value; |
| 50 |
bool operator<(Entry const& other) const |
| 51 |
{ |
| 52 |
return score < other.score; |
| 53 |
} |
| 54 |
}; |
| 55 |
|
| 56 |
void IncrementScore(); |
| 57 |
|
| 58 |
std::vector<Entry> entries_; |
| 59 |
int max_entries_ = 1; |
| 60 |
uint32_t next_score_ = 0; |
| 61 |
}; |
| 62 |
|
| 63 |
template<typename TKey, typename TValue> |
| 64 |
LruCache<TKey, TValue>::LruCache(int max_entries) : max_entries_(max_entries) |
| 65 |
{ |
| 66 |
assert(max_entries > 0); |
| 67 |
} |
| 68 |
|
| 69 |
template<typename TKey, typename TValue> |
| 70 |
template<typename TAllocator> |
| 71 |
TValue LruCache<TKey, TValue>::Get(TKey const& key, TAllocator allocator) |
| 72 |
{ |
| 73 |
for (Entry& entry : entries_) |
| 74 |
{ |
| 75 |
if (entry.key == key) |
| 76 |
{ |
| 77 |
return entry.value; |
| 78 |
} |
| 79 |
} |
| 80 |
|
| 81 |
auto result = allocator(); |
| 82 |
Insert(key, result); |
| 83 |
return result; |
| 84 |
} |
| 85 |
|
| 86 |
template<typename TKey, typename TValue> |
| 87 |
bool LruCache<TKey, TValue>::Has(TKey const& key) |
| 88 |
{ |
| 89 |
for (Entry& entry : entries_) |
| 90 |
{ |
| 91 |
if (entry.key == key) |
| 92 |
{ |
| 93 |
return true; |
| 94 |
} |
| 95 |
} |
| 96 |
return false; |
| 97 |
} |
| 98 |
|
| 99 |
template<typename TKey, typename TValue> |
| 100 |
bool LruCache<TKey, TValue>::TryGet(TKey const& key, TValue* dest) |
| 101 |
{ |
| 102 |
// Assign new score. |
| 103 |
for (Entry& entry : entries_) |
| 104 |
{ |
| 105 |
if (entry.key == key) |
| 106 |
{ |
| 107 |
entry.score = next_score_; |
| 108 |
IncrementScore(); |
| 109 |
if (dest) |
| 110 |
{ |
| 111 |
*dest = entry.value; |
| 112 |
} |
| 113 |
return true; |
| 114 |
} |
| 115 |
} |
| 116 |
|
| 117 |
return false; |
| 118 |
} |
| 119 |
|
| 120 |
template<typename TKey, typename TValue> |
| 121 |
bool LruCache<TKey, TValue>::TryTake(TKey const& key, TValue* dest) |
| 122 |
{ |
| 123 |
for (size_t i = 0; i < entries_.size(); ++i) |
| 124 |
{ |
| 125 |
if (entries_[i].key == key) |
| 126 |
{ |
| 127 |
if (dest) |
| 128 |
{ |
| 129 |
*dest = entries_[i].value; |
| 130 |
} |
| 131 |
entries_.erase(entries_.begin() + i); |
| 132 |
return true; |
| 133 |
} |
| 134 |
} |
| 135 |
|
| 136 |
return false; |
| 137 |
} |
| 138 |
|
| 139 |
template<typename TKey, typename TValue> |
| 140 |
void LruCache<TKey, TValue>::Insert(TKey const& key, TValue const& value) |
| 141 |
{ |
| 142 |
if ((int)entries_.size() >= max_entries_) |
| 143 |
{ |
| 144 |
entries_.erase(std::min_element(entries_.begin(), entries_.end())); |
| 145 |
} |
| 146 |
|
| 147 |
Entry entry; |
| 148 |
entry.score = next_score_; |
| 149 |
IncrementScore(); |
| 150 |
entry.key = key; |
| 151 |
entry.value = value; |
| 152 |
entries_.push_back(entry); |
| 153 |
} |
| 154 |
|
| 155 |
template<typename TKey, typename TValue> |
| 156 |
template<typename TFunc> |
| 157 |
void LruCache<TKey, TValue>::IterateValues(TFunc func) |
| 158 |
{ |
| 159 |
for (Entry& entry : entries_) |
| 160 |
{ |
| 161 |
if (!func(entry.value)) |
| 162 |
{ |
| 163 |
break; |
| 164 |
} |
| 165 |
} |
| 166 |
} |
| 167 |
|
| 168 |
template<typename TKey, typename TValue> |
| 169 |
void LruCache<TKey, TValue>::IncrementScore() |
| 170 |
{ |
| 171 |
// Overflow. |
| 172 |
if (++next_score_ == 0) |
| 173 |
{ |
| 174 |
std::sort(entries_.begin(), entries_.end()); |
| 175 |
for (Entry& entry : entries_) |
| 176 |
{ |
| 177 |
entry.score = next_score_++; |
| 178 |
} |
| 179 |
} |
| 180 |
} |
| 181 |
|
| 182 |
template<typename TKey, typename TValue> |
| 183 |
void LruCache<TKey, TValue>::Clear(void) |
| 184 |
{ |
| 185 |
entries_.clear(); |
| 186 |
next_score_ = 0; |
| 187 |
} |