Files
@ r28396:ef195b601c72
Branch filter:
Location: cpp/openttd-patchpack/source/src/misc/lrucache.hpp
r28396:ef195b601c72
3.2 KiB
text/x-c++hdr
Fix: Pass townnameparts as parameter when testing townname based companyname. (#11685)
Length of returned string could vary and pass/fail the length check with a different
string than the final selection.
Length of returned string could vary and pass/fail the length check with a different
string than the final selection.
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 | /*
* 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 <unordered_map>
/**
* 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 */
|