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       89088 :     int64_t accessCounter{0};
      24             : 
      25             : public:
      26      178176 :     explicit unordered_lru_cache(size_t _maxSize = MaxSize, size_t _truncateThreshold = TruncateThreshold) :
      27       89088 :         maxSize(_maxSize),
      28       89088 :         truncateThreshold(_truncateThreshold == 0 ? _maxSize * 2 : _truncateThreshold)
      29       89088 :     {
      30             :         // either specify maxSize through template arguments or the constructor and fail otherwise
      31       89088 :         assert(_maxSize != 0);
      32      178176 :     }
      33             : 
      34             :     size_t max_size() const { return maxSize; }
      35             : 
      36             :     template<typename Value2>
      37     1355961 :     void _emplace(const Key& key, Value2&& v)
      38             :     {
      39     1355961 :         auto it = cacheMap.find(key);
      40     1355961 :         if (it == cacheMap.end()) {
      41     1063828 :             cacheMap.emplace(key, std::make_pair(std::forward<Value2>(v), accessCounter++));
      42     1063828 :         } else {
      43      292133 :             it->second.first = std::forward<Value2>(v);
      44      292133 :             it->second.second = accessCounter++;
      45             :         }
      46     1355961 :         truncate_if_needed();
      47     1355961 :     }
      48             : 
      49      192636 :     void emplace(const Key& key, Value&& v)
      50             :     {
      51      192636 :         _emplace(key, v);
      52      192636 :     }
      53             : 
      54     1163325 :     void insert(const Key& key, const Value& v)
      55             :     {
      56     1163325 :         _emplace(key, v);
      57     1163325 :     }
      58             : 
      59     6251597 :     bool get(const Key& key, Value& value)
      60             :     {
      61     6251597 :         auto it = cacheMap.find(key);
      62     6251597 :         if (it != cacheMap.end()) {
      63     4551384 :             it->second.second = accessCounter++;
      64     4551384 :             value = it->second.first;
      65     4551384 :             return true;
      66             :         }
      67     1700213 :         return false;
      68     6251597 :     }
      69             : 
      70          19 :     bool exists(const Key& key)
      71             :     {
      72          19 :         auto it = cacheMap.find(key);
      73          19 :         if (it != cacheMap.end()) {
      74           5 :             it->second.second = accessCounter++;
      75           5 :             return true;
      76             :         }
      77          14 :         return false;
      78          19 :     }
      79             : 
      80       25395 :     void erase(const Key& key)
      81             :     {
      82       25395 :         cacheMap.erase(key);
      83       25395 :     }
      84             : 
      85        1392 :     void clear()
      86             :     {
      87        1392 :         cacheMap.clear();
      88        1392 :     }
      89             : 
      90             : private:
      91     1355961 :     void truncate_if_needed()
      92             :     {
      93             :         typedef typename MapType::iterator Iterator;
      94             : 
      95     1355961 :         if (cacheMap.size() <= truncateThreshold) {
      96     1348865 :             return;
      97             :         }
      98             : 
      99        7096 :         std::vector<Iterator> vec;
     100        7096 :         vec.reserve(cacheMap.size());
     101      174070 :         for (auto it = cacheMap.begin(); it != cacheMap.end(); ++it) {
     102      166974 :             vec.emplace_back(it);
     103      166974 :         }
     104             :         // sort by last access time (descending order)
     105     1140601 :         std::sort(vec.begin(), vec.end(), [](const Iterator& it1, const Iterator& it2) {
     106     1133505 :             return it1->second.second > it2->second.second;
     107             :         });
     108             : 
     109       94131 :         for (size_t i = maxSize; i < vec.size(); i++) {
     110       87035 :             cacheMap.erase(vec[i]);
     111       87035 :         }
     112     1355961 :     }
     113             : };
     114             : 
     115             : #endif // BITCOIN_UNORDERED_LRU_CACHE_H