OpenTTD Source 20241224-master-gee860a5c8e
lrucache.hpp
Go to the documentation of this file.
1/*
2 * This file is part of OpenTTD.
3 * 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.
4 * 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.
5 * 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/>.
6 */
7
10#ifndef LRUCACHE_HPP
11#define LRUCACHE_HPP
12
13#include <utility>
14#include <unordered_map>
15
21template <class Tkey, class Tdata>
22class LRUCache {
23private:
24 typedef std::pair<Tkey, Tdata *> Tpair;
25 typedef typename std::list<Tpair>::iterator Titer;
26
27 std::list<Tpair> data;
28 std::unordered_map<Tkey, Titer> lookup;
29
30 const size_t capacity;
31
32public:
37 LRUCache(size_t max_items) : capacity(max_items) {}
38
44 inline bool Contains(const Tkey key)
45 {
46 return this->lookup.find(key) != this->lookup.end();
47 }
48
55 Tdata *Insert(const Tkey key, Tdata *item)
56 {
57 Tdata *old = nullptr;
58
59 if (this->Contains(key)) {
60 /* Replace old value. */
61 old = this->lookup[key]->second;
62 this->lookup[key]->second = item;
63 } else {
64 /* Delete least used item if maximum items cached. */
65 if (this->data.size() >= this->capacity) {
66 Tpair last = data.back();
67 this->lookup.erase(last.first);
68 this->data.pop_back();
69
70 old = last.second;
71 }
72
73 /* Insert new item. */
74 this->data.emplace_front(key, item);
75 this->lookup.emplace(key, this->data.begin());
76 }
77
78 return old;
79 }
80
85 inline Tdata *Pop()
86 {
87 if (this->data.empty()) return nullptr;
88
89 Tdata *value = this->data.back().second;
90 this->lookup.erase(this->data.back().first);
91 this->data.pop_back();
92 return value;
93 }
94
101 inline Tdata *Get(const Tkey key)
102 {
103 if (this->lookup.find(key) == this->lookup.end()) throw std::out_of_range("item not found");
104 /* Move to front if needed. */
105 this->data.splice(this->data.begin(), this->data, this->lookup[key]);
106
107 return this->data.front().second;
108 }
109};
110
111#endif /* LRUCACHE_HPP */
Size limited cache with a least recently used eviction strategy.
Definition lrucache.hpp:22
Tdata * Get(const Tkey key)
Get an item from the cache.
Definition lrucache.hpp:101
LRUCache(size_t max_items)
Construct new LRU cache map.
Definition lrucache.hpp:37
bool Contains(const Tkey key)
Test if a key is already contained in the cache.
Definition lrucache.hpp:44
Tdata * Pop()
Pop the least recently used item.
Definition lrucache.hpp:85
std::list< Tpair > data
Ordered list of all items.
Definition lrucache.hpp:27
const size_t capacity
Number of items to cache.
Definition lrucache.hpp:30
Tdata * Insert(const Tkey key, Tdata *item)
Insert a new data item with a specified key.
Definition lrucache.hpp:55
std::unordered_map< Tkey, Titer > lookup
Map of keys to items.
Definition lrucache.hpp:28