src/misc/lrucache.hpp

   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
   8 /** @file lrucache.hpp Size limited cache map with a least recently used eviction strategy. */
   9
  10 #ifndef LRUCACHE_HPP
  11 #define LRUCACHE_HPP
  12
  13 #include <utility>
  14 #include <unordered_map>
  15
  16 /**
  17  * Size limited cache with a least recently used eviction strategy.
  18  * @tparam Tkey Type of the cache key.
  19  * @tparam Tdata Type of the cache item. The cache will store a pointer of this type.
  20  */
  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;                         ///< Ordered list of all items.
  28         std::unordered_map<Tkey, Titer> lookup;  ///< Map of keys to items.
  29
  30         const size_t capacity; ///< Number of items to cache.
  31
  32 public:
  33         /**
  34          * Construct new LRU cache map.
  35          * @param max_items Number of items to store at most.
  36          */
  37         LRUCache(size_t max_items) : capacity(max_items) {}
  38
  39         /**
  40          * Test if a key is already contained in the cache.
  41          * @param key The key to search.
  42          * @return True, if the key was found.
  43          */
  44         inline bool Contains(const Tkey key)
  45         {
  46                 return this->lookup.find(key) != this->lookup.end();
  47         }
  48
  49         /**
  50          * Insert a new data item with a specified key.
  51          * @param key Key under which the item should be stored.
  52          * @param item Item to insert.
  53          * @return Evicted item or nullptr, if no item had to be evicted.
  54          */
  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.push_front(std::make_pair(key, item));
  75                         this->lookup.emplace(key, this->data.begin());
  76                 }
  77
  78                 return old;
  79         }
  80
  81         /**
  82          * Pop the least recently used item.
  83          * @return The item value or nullptr if no items cached.
  84          */
  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
  95         /**
  96          * Get an item from the cache.
  97          * @param key The key to look up.
  98          * @return The item value.
  99          * @note Throws if item not found.
 100          */
 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 */