lrucache.hpp

Go to the documentation of this file.

/*
 * 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/>.
 */
 
#ifndef LRUCACHE_HPP
#define LRUCACHE_HPP
 
#include <utility>
#include <unordered_map>
 
template <class Tkey, class Tdata, class Thash = std::hash<Tkey>, class Tequality = std::equal_to<>>
class LRUCache {
private:
  using PairType = std::pair<Tkey, Tdata>;
  using StorageType = std::list<PairType>;
  using IteratorType = StorageType::iterator;
  using LookupType = std::unordered_map<Tkey, IteratorType, Thash, Tequality>;
 
  StorageType data; 
  LookupType lookup; 
 
  const size_t capacity; 
 
public:
  LRUCache(size_t max_items) : capacity(max_items) {}
 
  inline bool Contains(const Tkey &key)
  {
    return this->lookup.find(key) != this->lookup.end();
  }
  inline bool Contains(const Tkey &key) {…}
 
  void Insert(const Tkey &key, Tdata &&item)
  {
    auto it = this->lookup.find(key);
    if (it != this->lookup.end()) {
      /* Replace old value. */
      it->second->second = std::move(item);
      return;
    }
 
    /* Delete least used item if maximum items cached. */
    if (this->data.size() >= this->capacity) {
      this->lookup.erase(data.back().first);
      this->data.pop_back();
    }
 
    /* Insert new item. */
    this->data.emplace_front(key, std::move(item));
    this->lookup.emplace(key, this->data.begin());
  }
  void Insert(const Tkey &key, Tdata &&item) {…}
 
  void Clear()
  {
    this->lookup.clear();
    this->data.clear();
  }
  void Clear() {…}
 
  inline const Tdata &Get(const Tkey &key)
  {
    auto it = this->lookup.find(key);
    if (it == this->lookup.end()) throw std::out_of_range("item not found");
    /* Move to front if needed. */
    this->data.splice(this->data.begin(), this->data, it->second);
 
    return this->data.front().second;
  }
  inline const Tdata &Get(const Tkey &key) {…}
 
  inline Tdata *GetIfValid(const auto &key)
  {
    auto it = this->lookup.find(key);
    if (it == this->lookup.end()) return nullptr;
 
    /* Move to front if needed. */
    this->data.splice(this->data.begin(), this->data, it->second);
 
    return &this->data.front().second;
  }
  inline Tdata *GetIfValid(const auto &key) {…}
};
class LRUCache {…};
 
#endif /* LRUCACHE_HPP */