Line data    Source code

       1             : // Copyright (c) 2012-2018 The Bitcoin 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_LIMITEDMAP_H
       6             : #define BITCOIN_LIMITEDMAP_H
       7             : 
       8             : #include <assert.h>
       9             : #include <map>
      10             : 
      11             : /** STL-like map container that only keeps the N elements with the highest value. */
      12             : template <typename K, typename V>
      13        1282 : class limitedmap
      14             : {
      15             : public:
      16             :     typedef K key_type;
      17             :     typedef V mapped_type;
      18             :     typedef std::pair<const key_type, mapped_type> value_type;
      19             :     typedef typename std::map<K, V>::const_iterator const_iterator;
      20             :     typedef typename std::map<K, V>::size_type size_type;
      21             : 
      22             : protected:
      23             :     std::map<K, V> map;
      24             :     typedef typename std::map<K, V>::iterator iterator;
      25             :     std::multimap<V, iterator> rmap;
      26             :     typedef typename std::multimap<V, iterator>::iterator rmap_iterator;
      27             :     size_type nMaxSize;
      28             : 
      29             : public:
      30        1282 :     explicit limitedmap(size_type nMaxSizeIn)
      31         641 :     {
      32         641 :         assert(nMaxSizeIn > 0);
      33         641 :         nMaxSize = nMaxSizeIn;
      34        1282 :     }
      35           1 :     const_iterator begin() const { return map.begin(); }
      36       29941 :     const_iterator end() const { return map.end(); }
      37           5 :     size_type size() const { return map.size(); }
      38           1 :     bool empty() const { return map.empty(); }
      39       29960 :     const_iterator find(const key_type& k) const { return map.find(k); }
      40          22 :     size_type count(const key_type& k) const { return map.count(k); }
      41        9536 :     void insert(const value_type& x)
      42             :     {
      43        9536 :         std::pair<iterator, bool> ret = map.insert(x);
      44        9536 :         if (ret.second) {
      45        9536 :             if (map.size() > nMaxSize) {
      46           1 :                 map.erase(rmap.begin()->second);
      47           1 :                 rmap.erase(rmap.begin());
      48           1 :             }
      49        9536 :             rmap.insert(make_pair(x.second, ret.first));
      50        9536 :         }
      51        9536 :     }
      52       19354 :     void erase(const key_type& k)
      53             :     {
      54       19354 :         iterator itTarget = map.find(k);
      55       19354 :         if (itTarget == map.end())
      56        9930 :             return;
      57        9424 :         std::pair<rmap_iterator, rmap_iterator> itPair = rmap.equal_range(itTarget->second);
      58       18848 :         for (rmap_iterator it = itPair.first; it != itPair.second; ++it)
      59        9424 :             if (it->second == itTarget) {
      60        9424 :                 rmap.erase(it);
      61        9424 :                 map.erase(itTarget);
      62        9424 :                 return;
      63             :             }
      64             :         // Shouldn't ever get here
      65           0 :         assert(0);
      66       19354 :     }
      67          19 :     void update(const_iterator itIn, const mapped_type& v)
      68             :     {
      69             :         // Using map::erase() with empty range instead of map::find() to get a non-const iterator,
      70             :         // since it is a constant time operation in C++11. For more details, see
      71             :         // https://stackoverflow.com/questions/765148/how-to-remove-constness-of-const-iterator
      72          19 :         iterator itTarget = map.erase(itIn, itIn);
      73             : 
      74          19 :         if (itTarget == map.end())
      75           0 :             return;
      76          19 :         std::pair<rmap_iterator, rmap_iterator> itPair = rmap.equal_range(itTarget->second);
      77          38 :         for (rmap_iterator it = itPair.first; it != itPair.second; ++it)
      78          19 :             if (it->second == itTarget) {
      79          19 :                 rmap.erase(it);
      80          19 :                 itTarget->second = v;
      81          19 :                 rmap.insert(make_pair(v, itTarget));
      82          19 :                 return;
      83             :             }
      84             :         // Shouldn't ever get here
      85           0 :         assert(0);
      86          19 :     }
      87           2 :     size_type max_size() const { return nMaxSize; }
      88           1 :     size_type max_size(size_type s)
      89             :     {
      90           1 :         assert(s > 0);
      91           6 :         while (map.size() > s) {
      92           5 :             map.erase(rmap.begin()->second);
      93           5 :             rmap.erase(rmap.begin());
      94             :         }
      95           1 :         nMaxSize = s;
      96           1 :         return nMaxSize;
      97             :     }
      98             : };
      99             : 
     100             : #endif // BITCOIN_LIMITEDMAP_H