OpenTTD Source  1.11.0-beta2
lrucache.hpp
Go to the documentation of this file.
1 /* $Id$ */
2 
3 /*
4  * This file is part of OpenTTD.
5  * 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.
6  * 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.
7  * 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/>.
8  */
9 
12 #ifndef LRUCACHE_HPP
13 #define LRUCACHE_HPP
14 
15 #include <utility>
16 #include <list>
17 #include <functional>
18 #include <unordered_map>
19 #include <stdexcept>
20 
26 template <class Tkey, class Tdata>
27 class LRUCache {
28 private:
29  typedef std::pair<Tkey, Tdata *> Tpair;
30  typedef typename std::list<Tpair>::iterator Titer;
31 
32  std::list<Tpair> data;
33  std::unordered_map<Tkey, Titer> lookup;
34 
35  const size_t capacity;
36 
37 public:
42  LRUCache(size_t max_items) : capacity(max_items) {}
43 
49  inline bool Contains(const Tkey key)
50  {
51  return this->lookup.find(key) != this->lookup.end();
52  }
53 
60  Tdata *Insert(const Tkey key, Tdata *item)
61  {
62  Tdata *old = nullptr;
63 
64  if (this->Contains(key)) {
65  /* Replace old value. */
66  old = this->lookup[key]->second;
67  this->lookup[key]->second = item;
68  } else {
69  /* Delete least used item if maximum items cached. */
70  if (this->data.size() >= this->capacity) {
71  Tpair last = data.back();
72  this->lookup.erase(last.first);
73  this->data.pop_back();
74 
75  old = last.second;
76  }
77 
78  /* Insert new item. */
79  this->data.push_front(std::make_pair(key, item));
80  this->lookup.emplace(key, this->data.begin());
81  }
82 
83  return old;
84  }
85 
90  inline Tdata *Pop()
91  {
92  if (this->data.empty()) return nullptr;
93 
94  Tdata *value = this->data.back().second;
95  this->lookup.erase(this->data.back().first);
96  this->data.pop_back();
97  return value;
98  }
99 
106  inline Tdata *Get(const Tkey key)
107  {
108  if (this->lookup.find(key) == this->lookup.end()) throw std::out_of_range("item not found");
109  /* Move to front if needed. */
110  this->data.splice(this->data.begin(), this->data, this->lookup[key]);
111 
112  return this->data.front().second;
113  }
114 };
115 
116 #endif /* LRUCACHE_HPP */
LRUCache::Get
Tdata * Get(const Tkey key)
Get an item from the cache.
Definition: lrucache.hpp:106
LRUCache::Pop
Tdata * Pop()
Pop the least recently used item.
Definition: lrucache.hpp:90
LRUCache
Size limited cache with a least recently used eviction strategy.
Definition: lrucache.hpp:27
LRUCache::LRUCache
LRUCache(size_t max_items)
Construct new LRU cache map.
Definition: lrucache.hpp:42
LRUCache::Contains
bool Contains(const Tkey key)
Test if a key is already contained in the cache.
Definition: lrucache.hpp:49
LRUCache::capacity
const size_t capacity
Number of items to cache.
Definition: lrucache.hpp:35
LRUCache::Insert
Tdata * Insert(const Tkey key, Tdata *item)
Insert a new data item with a specified key.
Definition: lrucache.hpp:60
LRUCache::data
std::list< Tpair > data
Ordered list of all items.
Definition: lrucache.hpp:32
LRUCache::lookup
std::unordered_map< Tkey, Titer > lookup
Map of keys to items.
Definition: lrucache.hpp:33