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
|
// Modified version of: https://www.boost.org/doc/libs/1_79_0/boost/compute/detail/lru_cache.hpp
// Most important change is the use of an array instead of a map, so that elements are
// statically allocated. The insert and get methods have been merged into the request method.
// Original license:
//
//---------------------------------------------------------------------------//
// Copyright (c) 2013 Kyle Lutz <kyle.r.lutz@gmail.com>
//
// Distributed under the Boost Software License, Version 1.0
// See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt
//
// See http://boostorg.github.com/compute for more information.
//---------------------------------------------------------------------------//
#pragma once
#include <array>
#include <list>
#include <tuple>
#include <utility>
namespace Common {
// a cache which evicts the least recently used item when it is full
// the cache elements are statically allocated.
template <class Key, class Value, std::size_t Size>
class StaticLRUCache {
public:
using key_type = Key;
using value_type = Value;
using list_type = std::list<std::pair<Key, std::size_t>>;
using array_type = std::array<Value, Size>;
StaticLRUCache() = default;
~StaticLRUCache() = default;
std::size_t size() const {
return m_list.size();
}
constexpr std::size_t capacity() const {
return m_array.size();
}
bool empty() const {
return m_list.empty();
}
bool contains(const key_type& key) const {
return find(key) != m_list.end();
}
// Requests an element from the cache. If it is not found,
// the element is inserted using its key.
// Returns whether the element was present in the cache
// and a reference to the element itself.
std::pair<bool, value_type&> request(const key_type& key) {
// lookup value in the cache
auto i = find(key);
if (i == m_list.cend()) {
std::size_t next_index = size();
// insert item into the cache, but first check if it is full
if (next_index >= capacity()) {
// cache is full, evict the least recently used item
next_index = evict();
}
// insert the new item
m_list.push_front(std::make_pair(key, next_index));
return std::pair<bool, value_type&>(false, m_array[next_index]);
}
// return the value, but first update its place in the most
// recently used list
if (i != m_list.cbegin()) {
// move item to the front of the most recently used list
auto backup = *i;
m_list.erase(i);
m_list.push_front(backup);
// return the value
return std::pair<bool, value_type&>(true, m_array[backup.second]);
} else {
// the item is already at the front of the most recently
// used list so just return it
return std::pair<bool, value_type&>(true, m_array[i->second]);
}
}
void clear() {
m_list.clear();
}
private:
typename list_type::const_iterator find(const key_type& key) const {
return std::find_if(m_list.cbegin(), m_list.cend(),
[&key](const auto& el) { return el.first == key; });
}
std::size_t evict() {
// evict item from the end of most recently used list
typename list_type::iterator i = --m_list.end();
std::size_t evicted_index = i->second;
m_list.erase(i);
return evicted_index;
}
private:
array_type m_array;
list_type m_list;
};
} // namespace Common
|
