duckstation

duckstation, but archived from the revision just before upstream changed it to a proprietary software project, this version is the libre one
git clone https://git.neptards.moe/u3shit/duckstation.git
Log | Files | Refs | README | LICENSE

lru_cache.h (2832B)

      1 // SPDX-FileCopyrightText: 2019-2022 Connor McLaughlin <stenzek@gmail.com>
      2 // SPDX-License-Identifier: (GPL-3.0 OR CC-BY-NC-ND-4.0)
      3 
      4 #pragma once
      5 #include "heterogeneous_containers.h"
      6 #include <cstdint>
      7 #include <map>
      8 
      9 template<class K, class V>
     10 class LRUCache
     11 {
     12   using CounterType = std::uint64_t;
     13 
     14   struct Item
     15   {
     16     V value;
     17     CounterType last_access;
     18   };
     19 
     20   using MapType = std::conditional_t<std::is_same_v<K, std::string>, StringMap<Item>, std::map<K, Item>>;
     21 
     22 public:
     23   LRUCache(std::size_t max_capacity = 16, bool manual_evict = false)
     24     : m_max_capacity(max_capacity), m_manual_evict(manual_evict)
     25   {
     26   }
     27   ~LRUCache() = default;
     28 
     29   std::size_t GetSize() const { return m_items.size(); }
     30   std::size_t GetMaxCapacity() const { return m_max_capacity; }
     31 
     32   void Clear() { m_items.clear(); }
     33 
     34   void SetMaxCapacity(std::size_t capacity)
     35   {
     36     m_max_capacity = capacity;
     37     if (m_items.size() > m_max_capacity)
     38       Evict(m_items.size() - m_max_capacity);
     39   }
     40 
     41   template<typename KeyT>
     42   V* Lookup(const KeyT& key)
     43   {
     44     auto iter = m_items.find(key);
     45     if (iter == m_items.end())
     46       return nullptr;
     47 
     48     iter->second.last_access = ++m_last_counter;
     49     return &iter->second.value;
     50   }
     51 
     52   V* Insert(K key, V value)
     53   {
     54     ShrinkForNewItem();
     55 
     56     auto iter = m_items.find(key);
     57     if (iter != m_items.end())
     58     {
     59       iter->second.value = std::move(value);
     60       iter->second.last_access = ++m_last_counter;
     61       return &iter->second.value;
     62     }
     63     else
     64     {
     65       Item it;
     66       it.last_access = ++m_last_counter;
     67       it.value = std::move(value);
     68       auto ip = m_items.emplace(std::move(key), std::move(it));
     69       return &ip.first->second.value;
     70     }
     71   }
     72 
     73   void Evict(std::size_t count = 1)
     74   {
     75     while (!m_items.empty() && count > 0)
     76     {
     77       typename MapType::iterator lowest = m_items.end();
     78       for (auto iter = m_items.begin(); iter != m_items.end(); ++iter)
     79       {
     80         if (lowest == m_items.end() || iter->second.last_access < lowest->second.last_access)
     81           lowest = iter;
     82       }
     83       m_items.erase(lowest);
     84       count--;
     85     }
     86   }
     87 
     88   template<typename KeyT>
     89   bool Remove(const KeyT& key)
     90   {
     91     auto iter = m_items.find(key);
     92     if (iter == m_items.end())
     93       return false;
     94     m_items.erase(iter);
     95     return true;
     96   }
     97   void SetManualEvict(bool block)
     98   {
     99     m_manual_evict = block;
    100     if (!m_manual_evict)
    101       ManualEvict();
    102   }
    103   void ManualEvict()
    104   {
    105     // evict if we went over
    106     while (m_items.size() > m_max_capacity)
    107       Evict(m_items.size() - m_max_capacity);
    108   }
    109 
    110 private:
    111   void ShrinkForNewItem()
    112   {
    113     if (m_items.size() < m_max_capacity)
    114       return;
    115 
    116     Evict(m_items.size() - (m_max_capacity - 1));
    117   }
    118 
    119   MapType m_items;
    120   CounterType m_last_counter = 0;
    121   std::size_t m_max_capacity = 0;
    122   bool m_manual_evict = false;
    123 };