Line data    Source code

       1             : // Copyright (c) 2014-2025 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_CACHEMULTIMAP_H
       6             : #define BITCOIN_CACHEMULTIMAP_H
       7             : 
       8             : #include <cstddef>
       9             : #include <map>
      10             : #include <list>
      11             : #include <set>
      12             : 
      13             : #include <serialize.h>
      14             : 
      15             : #include <cachemap.h>
      16             : 
      17             : /**
      18             :  * Map like container that keeps the N most recently added items
      19             :  */
      20             : template<typename K, typename V, typename Size = uint32_t>
      21           1 : class CacheMultiMap
      22             : {
      23             : public:
      24             :     using size_type = Size;
      25             : 
      26             :     using item_t = CacheItem<K,V>;
      27             : 
      28             :     using list_t = std::list<item_t>;
      29             : 
      30             :     using list_it = typename list_t::iterator;
      31             : 
      32             :     using list_cit = typename list_t::const_iterator;
      33             : 
      34             :     using it_map_t = std::map<V,list_it>;
      35             : 
      36             :     using it_map_it = typename it_map_t::iterator;
      37             : 
      38             :     using it_map_cit = typename it_map_t::const_iterator;
      39             : 
      40             :     using map_t = std::map<K, it_map_t>;
      41             : 
      42             :     using map_it = typename map_t::iterator;
      43             : 
      44             :     using map_cit = typename map_t::const_iterator;
      45             : 
      46             : private:
      47             :     size_type nMaxSize;
      48             : 
      49             :     list_t listItems;
      50             : 
      51             :     map_t mapIndex;
      52             : 
      53             : public:
      54         362 :     explicit CacheMultiMap(size_type nMaxSizeIn = 0)
      55         181 :         : nMaxSize(nMaxSizeIn),
      56         181 :           listItems(),
      57         181 :           mapIndex()
      58         362 :     {}
      59             : 
      60             :     explicit CacheMultiMap(const CacheMap<K,V>& other)
      61             :         : nMaxSize(other.nMaxSize),
      62             :           listItems(other.listItems),
      63             :           mapIndex()
      64             :     {
      65             :         RebuildIndex();
      66             :     }
      67             : 
      68           0 :     void Clear()
      69             :     {
      70           0 :         mapIndex.clear();
      71           0 :         listItems.clear();
      72           0 :     }
      73             : 
      74             :     void SetMaxSize(size_type nMaxSizeIn)
      75             :     {
      76             :         nMaxSize = nMaxSizeIn;
      77             :     }
      78             : 
      79           7 :     size_type GetMaxSize() const {
      80           7 :         return nMaxSize;
      81             :     }
      82             : 
      83          12 :     size_type GetSize() const {
      84          12 :         return listItems.size();
      85             :     }
      86             : 
      87          14 :     bool Insert(const K& key, const V& value)
      88             :     {
      89          14 :         map_it mit = mapIndex.find(key);
      90          14 :         if(mit == mapIndex.end()) {
      91          12 :             mit = mapIndex.emplace(key, it_map_t()).first;
      92          12 :         }
      93          14 :         it_map_t& mapIt = mit->second;
      94             : 
      95          14 :         if(mapIt.count(value) > 0) {
      96             :             // Don't insert duplicates
      97           0 :             return false;
      98             :         }
      99             : 
     100          14 :         if(listItems.size() == nMaxSize) {
     101           3 :             PruneLast();
     102           3 :         }
     103          14 :         listItems.push_front(item_t(key, value));
     104          14 :         mapIt.emplace(value, listItems.begin());
     105          14 :         return true;
     106          14 :     }
     107             : 
     108           6 :     bool HasKey(const K& key) const
     109             :     {
     110           6 :         return (mapIndex.find(key) != mapIndex.end());
     111             :     }
     112             : 
     113          19 :     bool Get(const K& key, V& value) const
     114             :     {
     115          19 :         map_cit it = mapIndex.find(key);
     116          19 :         if(it == mapIndex.end()) {
     117           0 :             return false;
     118             :         }
     119          19 :         const it_map_t& mapIt = it->second;
     120          19 :         const item_t& item = *(mapIt.begin()->second);
     121          19 :         value = item.value;
     122          19 :         return true;
     123          19 :     }
     124             : 
     125           2 :     bool GetAll(const K& key, std::vector<V>& vecValues)
     126             :     {
     127           2 :         map_cit mit = mapIndex.find(key);
     128           2 :         if(mit == mapIndex.end()) {
     129           0 :             return false;
     130             :         }
     131           2 :         const it_map_t& mapIt = mit->second;
     132             : 
     133           8 :         for(it_map_cit it = mapIt.begin(); it != mapIt.end(); ++it) {
     134           6 :             const item_t& item = *(it->second);
     135           6 :             vecValues.push_back(item.value);
     136           6 :         }
     137           2 :         return true;
     138           2 :     }
     139             : 
     140           0 :     void GetKeys(std::vector<K>& vecKeys)
     141             :     {
     142           0 :         for(map_cit it = mapIndex.begin(); it != mapIndex.end(); ++it) {
     143           0 :             vecKeys.push_back(it->first);
     144           0 :         }
     145           0 :     }
     146             : 
     147           1 :     void Erase(const K& key)
     148             :     {
     149           1 :         map_it mit = mapIndex.find(key);
     150           1 :         if(mit == mapIndex.end()) {
     151           0 :             return;
     152             :         }
     153           1 :         const it_map_t& mapIt = mit->second;
     154             : 
     155           2 :         for (const auto& it : mapIt) {
     156           1 :             listItems.erase(it.second);
     157             :         }
     158             : 
     159           1 :         mapIndex.erase(mit);
     160           1 :     }
     161             : 
     162           0 :     void Erase(const K& key, const V& value)
     163             :     {
     164           0 :         map_it mit = mapIndex.find(key);
     165           0 :         if(mit == mapIndex.end()) {
     166           0 :             return;
     167             :         }
     168           0 :         it_map_t& mapIt = mit->second;
     169             : 
     170           0 :         it_map_it it = mapIt.find(value);
     171           0 :         if(it == mapIt.end()) {
     172           0 :             return;
     173             :         }
     174             : 
     175           0 :         listItems.erase(it->second);
     176           0 :         mapIt.erase(it);
     177             : 
     178           0 :         if(mapIt.empty()) {
     179           0 :             mapIndex.erase(mit);
     180           0 :         }
     181           0 :     }
     182             : 
     183           6 :     const list_t& GetItemList() const {
     184           6 :         return listItems;
     185             :     }
     186             : 
     187             :     CacheMap<K,V>& operator=(const CacheMap<K,V>& other)
     188             :     {
     189             :         nMaxSize = other.nMaxSize;
     190             :         listItems = other.listItems;
     191             :         RebuildIndex();
     192             :         return *this;
     193             :     }
     194             : 
     195           6 :     SERIALIZE_METHODS(CacheMultiMap, obj)
     196             :     {
     197           2 :         READWRITE(obj.nMaxSize, obj.listItems);
     198           3 :         SER_READ(obj, obj.RebuildIndex());
     199           2 :     }
     200             : 
     201             : private:
     202           3 :     void PruneLast()
     203             :     {
     204           3 :         if(listItems.empty()) {
     205           0 :             return;
     206             :         }
     207             : 
     208           3 :         list_it lit = listItems.end();
     209           3 :         --lit;
     210           3 :         item_t& item = *lit;
     211             : 
     212           3 :         map_it mit = mapIndex.find(item.key);
     213             : 
     214           3 :         if(mit != mapIndex.end()) {
     215           3 :             it_map_t& mapIt = mit->second;
     216             : 
     217           3 :             mapIt.erase(item.value);
     218             : 
     219           3 :             if(mapIt.empty()) {
     220           3 :                 mapIndex.erase(item.key);
     221           3 :             }
     222           3 :         }
     223             : 
     224           3 :         listItems.pop_back();
     225           3 :     }
     226             : 
     227           1 :     void RebuildIndex()
     228             :     {
     229           1 :         mapIndex.clear();
     230          11 :         for(list_it lit = listItems.begin(); lit != listItems.end(); ++lit) {
     231          10 :             item_t& item = *lit;
     232          10 :             map_it mit = mapIndex.find(item.key);
     233          10 :             if(mit == mapIndex.end()) {
     234           8 :                 mit = mapIndex.emplace(item.key, it_map_t()).first;
     235           8 :             }
     236          10 :             it_map_t& mapIt = mit->second;
     237          10 :             mapIt.emplace(item.value, lit);
     238          10 :         }
     239           1 :     }
     240             : };
     241             : 
     242             : #endif // BITCOIN_CACHEMULTIMAP_H