Line data    Source code

       1             : // Copyright (c) 2019-2023 The Dash Core developers
       2             : // Distributed under the MIT software license, see the accompanying
       3             : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
       4             : 
       5             : #ifndef BITCOIN_UNORDERED_LRU_CACHE_H
       6             : #define BITCOIN_UNORDERED_LRU_CACHE_H
       7             : 
       8             : #include <algorithm>
       9             : #include <cassert>
      10             : #include <cstdint>
      11             : #include <unordered_map>
      12             : #include <vector>
      13             : 
      14             : template<typename Key, typename Value, typename Hasher, size_t MaxSize = 0, size_t TruncateThreshold = 0>
      15             : class unordered_lru_cache
      16             : {
      17             : private:
      18             :     typedef std::unordered_map<Key, std::pair<Value, int64_t>, Hasher> MapType;
      19             : 
      20             :     MapType cacheMap;
      21             :     size_t maxSize;
      22             :     size_t truncateThreshold;
      23        4475 :     int64_t accessCounter{0};
      24             : 
      25             : public:
      26        8950 :     explicit unordered_lru_cache(size_t _maxSize = MaxSize, size_t _truncateThreshold = TruncateThreshold) :
      27        4475 :         maxSize(_maxSize),
      28        4475 :         truncateThreshold(_truncateThreshold == 0 ? _maxSize * 2 : _truncateThreshold)
      29        4475 :     {
      30             :         // either specify maxSize through template arguments or the constructor and fail otherwise
      31        4475 :         assert(_maxSize != 0);
      32        8950 :     }
      33             : 
      34             :     size_t max_size() const { return maxSize; }
      35             : 
      36             :     template<typename Value2>
      37       43613 :     void _emplace(const Key& key, Value2&& v)
      38             :     {
      39       43613 :         auto it = cacheMap.find(key);
      40       43613 :         if (it == cacheMap.end()) {
      41       43609 :             cacheMap.emplace(key, std::make_pair(std::forward<Value2>(v), accessCounter++));
      42       43609 :         } else {
      43           4 :             it->second.first = std::forward<Value2>(v);
      44           4 :             it->second.second = accessCounter++;
      45             :         }
      46       43613 :         truncate_if_needed();
      47       43613 :     }
      48             : 
      49        1566 :     void emplace(const Key& key, Value&& v)
      50             :     {
      51        1566 :         _emplace(key, v);
      52        1566 :     }
      53             : 
      54       42047 :     void insert(const Key& key, const Value& v)
      55             :     {
      56       42047 :         _emplace(key, v);
      57       42047 :     }
      58             : 
      59      795603 :     bool get(const Key& key, Value& value)
      60             :     {
      61      795603 :         auto it = cacheMap.find(key);
      62      795603 :         if (it != cacheMap.end()) {
      63      178799 :             it->second.second = accessCounter++;
      64      178799 :             value = it->second.first;
      65      178799 :             return true;
      66             :         }
      67      616804 :         return false;
      68      795603 :     }
      69             : 
      70           0 :     bool exists(const Key& key)
      71             :     {
      72           0 :         auto it = cacheMap.find(key);
      73           0 :         if (it != cacheMap.end()) {
      74           0 :             it->second.second = accessCounter++;
      75           0 :             return true;
      76             :         }
      77           0 :         return false;
      78           0 :     }
      79             : 
      80           0 :     void erase(const Key& key)
      81             :     {
      82           0 :         cacheMap.erase(key);
      83           0 :     }
      84             : 
      85          32 :     void clear()
      86             :     {
      87          32 :         cacheMap.clear();
      88          32 :     }
      89             : 
      90             : private:
      91       43613 :     void truncate_if_needed()
      92             :     {
      93             :         typedef typename MapType::iterator Iterator;
      94             : 
      95       43613 :         if (cacheMap.size() <= truncateThreshold) {
      96       42839 :             return;
      97             :         }
      98             : 
      99         774 :         std::vector<Iterator> vec;
     100         774 :         vec.reserve(cacheMap.size());
     101       22642 :         for (auto it = cacheMap.begin(); it != cacheMap.end(); ++it) {
     102       21868 :             vec.emplace_back(it);
     103       21868 :         }
     104             :         // sort by last access time (descending order)
     105      167224 :         std::sort(vec.begin(), vec.end(), [](const Iterator& it1, const Iterator& it2) {
     106      166450 :             return it1->second.second > it2->second.second;
     107             :         });
     108             : 
     109       12095 :         for (size_t i = maxSize; i < vec.size(); i++) {
     110       11321 :             cacheMap.erase(vec[i]);
     111       11321 :         }
     112       43613 :     }
     113             : };
     114             : 
     115             : #endif // BITCOIN_UNORDERED_LRU_CACHE_H