Line data    Source code

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