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
|
/* $Id$ */
/*
* This file is part of OpenTTD.
* OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
* OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
* See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
*/
/** @file lrucache.hpp Size limited cache map with a least recently used eviction strategy. */
#ifndef LRUCACHE_HPP
#define LRUCACHE_HPP
#include <utility>
#include <list>
#include <functional>
#include <unordered_map>
#include <stdexcept>
/**
* Size limited cache with a least recently used eviction strategy.
* @tparam Tkey Type of the cache key.
* @tparam Tdata Type of the cache item. The cache will store a pointer of this type.
*/
template <class Tkey, class Tdata>
class LRUCache {
private:
typedef std::pair<Tkey, Tdata *> Tpair;
typedef typename std::list<Tpair>::iterator Titer;
std::list<Tpair> data; ///< Ordered list of all items.
std::unordered_map<Tkey, Titer> lookup; ///< Map of keys to items.
const size_t capacity; ///< Number of items to cache.
public:
/**
* Construct new LRU cache map.
* @param max_items Number of items to store at most.
*/
LRUCache(size_t max_items) : capacity(max_items) {}
/**
* Test if a key is already contained in the cache.
* @param key The key to search.
* @return True, if the key was found.
*/
inline bool Contains(const Tkey key)
{
return this->lookup.find(key) != this->lookup.end();
}
/**
* Insert a new data item with a specified key.
* @param key Key under which the item should be stored.
* @param item Item to insert.
* @return Evicted item or nullptr, if no item had to be evicted.
*/
Tdata *Insert(const Tkey key, Tdata *item)
{
Tdata *old = nullptr;
if (this->Contains(key)) {
/* Replace old value. */
old = this->lookup[key]->second;
this->lookup[key]->second = item;
} else {
/* Delete least used item if maximum items cached. */
if (this->data.size() >= this->capacity) {
Tpair last = data.back();
this->lookup.erase(last.first);
this->data.pop_back();
old = last.second;
}
/* Insert new item. */
this->data.push_front(std::make_pair(key, item));
this->lookup.emplace(key, this->data.begin());
}
return old;
}
/**
* Pop the least recently used item.
* @return The item value or nullptr if no items cached.
*/
inline Tdata *Pop()
{
if (this->data.empty()) return nullptr;
Tdata *value = this->data.back().second;
this->lookup.erase(this->data.back().first);
this->data.pop_back();
return value;
}
/**
* Get an item from the cache.
* @param key The key to look up.
* @return The item value.
* @note Throws if item not found.
*/
inline Tdata *Get(const Tkey key)
{
if (this->lookup.find(key) == this->lookup.end()) throw std::out_of_range("item not found");
/* Move to front if needed. */
this->data.splice(this->data.begin(), this->data, this->lookup[key]);
return this->data.front().second;
}
};
#endif /* LRUCACHE_HPP */
|
