OpenTTD Source  20241108-master-g80f628063a
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 
21 template <class Tkey, class Tdata>
22 class LRUCache {
23 private:
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 
32 public:
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
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
std::list< Tpair > data
Ordered list of all items.
Definition: lrucache.hpp:27
Tdata * Get(const Tkey key)
Get an item from the cache.
Definition: lrucache.hpp:101
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
Tdata * Pop()
Pop the least recently used item.
Definition: lrucache.hpp:85