Line data    Source code

       1             : // Copyright (c) 2014-2023 The Dash Core developers
       2             : // Distributed under the MIT/X11 software license, see the accompanying
       3             : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
       4             : 
       5             : #ifndef BITCOIN_CACHEMAP_H
       6             : #define BITCOIN_CACHEMAP_H
       7             : 
       8             : #include <map>
       9             : #include <list>
      10             : #include <cstddef>
      11             : 
      12             : #include <serialize.h>
      13             : 
      14             : /**
      15             :  * Serializable structure for key/value items
      16             :  */
      17             : template<typename K, typename V>
      18             : struct CacheItem
      19             : {
      20          38 :     CacheItem()
      21          38 :     {}
      22             : 
      23        3010 :     CacheItem(const K& keyIn, const V& valueIn)
      24        1505 :     : key(keyIn),
      25        1505 :       value(valueIn)
      26        3010 :     {}
      27             : 
      28             :     K key;
      29             :     V value;
      30             : 
      31         114 :     SERIALIZE_METHODS(CacheItem, obj)
      32             :     {
      33          38 :         READWRITE(obj.key, obj.value);
      34          38 :     }
      35             : };
      36             : 
      37             : 
      38             : /**
      39             :  * Map like container that keeps the N most recently added items
      40             :  */
      41             : template<typename K, typename V, typename Size = uint32_t>
      42             : class CacheMap
      43             : {
      44             : public:
      45             :     using size_type = Size;
      46             : 
      47             :     using item_t = CacheItem<K,V>;
      48             : 
      49             :     using list_t = std::list<item_t>;
      50             : 
      51             :     using list_it = typename list_t::iterator;
      52             : 
      53             :     using list_cit = typename list_t::const_iterator;
      54             : 
      55             :     using map_t = std::map<K, list_it>;
      56             : 
      57             :     using map_it = typename map_t::iterator;
      58             : 
      59             :     using map_cit = typename map_t::const_iterator;
      60             : 
      61             : private:
      62             :     size_type nMaxSize;
      63             : 
      64             :     list_t listItems;
      65             : 
      66             :     map_t mapIndex;
      67             : 
      68             : public:
      69       19578 :     explicit CacheMap(size_type nMaxSizeIn = 0)
      70        9789 :         : nMaxSize(nMaxSizeIn),
      71        9789 :           listItems(),
      72        9789 :           mapIndex()
      73       19578 :     {}
      74             : 
      75           2 :     explicit CacheMap(const CacheMap<K,V>& other)
      76           1 :         : nMaxSize(other.nMaxSize),
      77           1 :           listItems(other.listItems),
      78           1 :           mapIndex()
      79           1 :     {
      80           1 :         RebuildIndex();
      81           2 :     }
      82             : 
      83        5356 :     void Clear()
      84             :     {
      85        5356 :         mapIndex.clear();
      86        5356 :         listItems.clear();
      87        5356 :     }
      88             : 
      89             :     void SetMaxSize(size_type nMaxSizeIn)
      90             :     {
      91             :         nMaxSize = nMaxSizeIn;
      92             :     }
      93             : 
      94           7 :     size_type GetMaxSize() const {
      95           7 :         return nMaxSize;
      96             :     }
      97             : 
      98      101197 :     size_type GetSize() const {
      99      101197 :         return listItems.size();
     100             :     }
     101             : 
     102        1492 :     bool Insert(const K& key, const V& value)
     103             :     {
     104        1492 :         if(mapIndex.find(key) != mapIndex.end()) {
     105           1 :             return false;
     106             :         }
     107        1491 :         if(listItems.size() == nMaxSize) {
     108           1 :             PruneLast();
     109           1 :         }
     110        1491 :         listItems.push_front(item_t(key, value));
     111        1491 :         mapIndex.emplace(key, listItems.begin());
     112        1491 :         return true;
     113        1492 :     }
     114             : 
     115        5930 :     bool HasKey(const K& key) const
     116             :     {
     117        5930 :         return (mapIndex.find(key) != mapIndex.end());
     118             :     }
     119             : 
     120        2522 :     bool Get(const K& key, V& value) const
     121             :     {
     122        2522 :         map_cit it = mapIndex.find(key);
     123        2522 :         if(it == mapIndex.end()) {
     124           0 :             return false;
     125             :         }
     126        2522 :         const item_t& item = *(it->second);
     127        2522 :         value = item.value;
     128        2522 :         return true;
     129        2522 :     }
     130             : 
     131         281 :     void Erase(const K& key)
     132             :     {
     133         281 :         map_it it = mapIndex.find(key);
     134         281 :         if(it == mapIndex.end()) {
     135           0 :             return;
     136             :         }
     137         281 :         listItems.erase(it->second);
     138         281 :         mapIndex.erase(it);
     139         281 :     }
     140             : 
     141          66 :     const list_t& GetItemList() const {
     142          66 :         return listItems;
     143             :     }
     144             : 
     145           1 :     CacheMap<K,V>& operator=(const CacheMap<K,V>& other)
     146             :     {
     147           1 :         nMaxSize = other.nMaxSize;
     148           1 :         listItems = other.listItems;
     149           1 :         RebuildIndex();
     150           1 :         return *this;
     151             :     }
     152             : 
     153       21384 :     SERIALIZE_METHODS(CacheMap, obj)
     154             :     {
     155        7128 :         READWRITE(obj.nMaxSize, obj.listItems);
     156       10539 :         SER_READ(obj, obj.RebuildIndex());
     157        7128 :     }
     158             : 
     159             : private:
     160           1 :     void PruneLast()
     161             :     {
     162           1 :         if(listItems.empty()) {
     163           0 :             return;
     164             :         }
     165           1 :         item_t& item = listItems.back();
     166           1 :         mapIndex.erase(item.key);
     167           1 :         listItems.pop_back();
     168           1 :     }
     169             : 
     170        3413 :     void RebuildIndex()
     171             :     {
     172        3413 :         mapIndex.clear();
     173        3440 :         for(list_it it = listItems.begin(); it != listItems.end(); ++it) {
     174          27 :             mapIndex.emplace(it->key, it);
     175          27 :         }
     176        3413 :     }
     177             : };
     178             : 
     179             : #endif // BITCOIN_CACHEMAP_H